It is not programmatically possible to ask the server what quests you have done and which you haven't. An addon is limited to what it saw you do, so unless you had the addon installed since you rolled the character, what you're asking for would not be possible.
Personally, I used TourGuide, because it's simple, lightweight, and I like Tekkub's stuff. But I did it on a DK, moving straight from EPL to the starter zones and methodically going through everything, so I didn't face the problem that you do. I'm at 2700 and counting, with Sholazar, Storm Peaks and Icecrown left, so I should get it easily.
You can still use something like TourGuide (it has guides covering all non-group quests from level 1 up), but when you find that it's telling you to pick up something that isn't being offered, just click on the objective and move on. So long as you follow it in order, you can be certain that any quests not being offered are ones that you've done, not ones that you're not eligible for because you didn't do a prerequisite.