With the release of Wrath of the Lich King there are many more daily quests added to WoW. However, unlike in BC where they were much easier to find, the Northrend Dailies are scattered all across the frozen waste land. My idea is to write an addon providing locations for these daily quests and be able to filter them by rep, zone, etc.
While this may sound like a good idea there is an issue I can for see that would cause problems and that would be Blizzard's usage of Phasing in this expansion. For example: most (if not all) of the Ebon Dailies have to be unlocked via a quest change in Icecrown. I do not believe there is a way to track the completion of this quest chain (unless through achievements or possibly your reputation status).
This is the only issue stopping me from writing this addon, but I believe if I can get past that somehow an addon like this would prove to be very useful.
You're correct in that there is no way to get information about which quests a character has completed through the API. However, you could avoid this. Simply show a note to the effect that "quests in this area require having completed the quest line ending with _____. If you need to do this quest line, it starts with _____ from _____ at _____." and keep track of which NPC needs to be available for each daily quest. Mark the location of each NPC, and once the user interacts with that NPC once (or even accepts the quest once), hide the note from that point on.