(or as it should more aptly be named, "How I drove myself absolutely batty over four days trying to find the most obscure quests imaginable")
(Apologies too, for I will not be posting links. I can't access game sites through a work proxy.)
First off, what I started with: Level 70 night elf hunter in T6 gear. I leveled primarily on quests and instances to 60 and was raiding pre-BC. I did Azeroth quests even after BC was released I hit 70, as I solo ground my way to Exalted Cenarion Circle and Argent Dawn (combination of quests, turn ins, kills, etc). I raided pre-BC up to and including intro AQ40 (but no ZG or AQ20). I did the attunement for BWL, MC and Onyxia. I had no Alliance factions to exalted. I had also done the Pirate rep many months ago, so all my goblin factions were hated. When the achievement system hit, it showed I was and sitting around ~450 quests in both Kalimdor and Eastern Kingdoms (that's each, so nearly ~900 quests in Azeroth done), and my Outlands Loremaster was already completed (I've done 100% of the quests, including dungeons, in Outlands prior to the achievements patch). I've been playing this toon for almost three years now, and have also leveled two alts to 70 and a third alt to 52. These alts were all leveled with the help of Jame's guide, but my main was leveled without anything. The most I would use would be Thotbot to get a list of all the quests in an area and I would keep a spreadsheet of them and delete them as I found them (I was a bit OCD with finishing *all* quests in a zone before moving on). I did most group quests at level, but some were dropped occasionally if I either grew bored, outleveled them, or just couldn't find any help. I did most of the dungeons at the proper level, but Dire Maul was never done until I was 70, and then I didn't actually grab quests for it at the time.
First off, apparently horde has it easier than Alliance for Kalimdor. I cannot agree or refute this, but these ideas should work if you transfer them over to your appropriate faction. There are also race-specific quests that you can be locked out of (I did the entire Draenei starting area on a draenei alt and was surprised at how many quests I wasn't able to get as a night elf).
Second, run with the low level quest tracker on *all the time*. It can be annoying if you can track other types of critters and you want to in order to make it easier to find them, but you may miss random quests. Especially if you quested in this area before the ! showed up on your mini map for items and stuff.
I first started by going to the Draenei starting zone and doing all the lowbie quests. Prepare to be bugged by lowbies for help/gold/whatever. Do them fast, don't bother looting unless you have to, and get out. Getting a list of all the quests that start in that zone through Wowhead.com will be a great help, especially if you haven't leveled a toon of that quest there.
After this, I went to the night elf starting zone and worked my way forward again. I didn't find anything here, since I was pretty thorough the first time.
In Darkshore, I discovered that I missed a lot of the dead critters by the sea shore. This is because when i went through there three years ago, items didn't display ! on the screen. You only found out about these if you moused over and got the action wheel. I picked up a few through here. This area was also easy for me to grab extra quests in because I had very systematically ran my Draenei through the quests in order to get exalted Darnassus a few months ago.
I then tried to go through each zone and hit the quest/flight hubs. I found Forest Song, which didn't exist back when I was leveling, and that helped. Then I hit up Theramore and that was a good chunk. But after that, I was blocked at around 650 quests.
This block was for one main reason... I was hated in all goblin cities and therefore blocked out of two major hubs that I had never quested in (Ratchet and Mudsprocket) and the occasional goblin would show up part way through a non-goblin questline and break it (HAY THERAMORE!). I was working on fixing Gadgetzan rep for another reason, but I wound up having to go full force with all the goblin towns. Even though a quest hub in Shimmering Flats had goblins, they weren't hating me, but they would send me to goblin towns such as Ratchet and Booty Bay. On top of that, I was getting *really* fed up with the flight points I couldn't access. Most of the time, I would port to Kalimdor through the Caverns of Time, but I was unable to use Gadgetzan, Un'Goro and Ratchet flight masters (you can fly into them, but be prepared to *run* or you will die. You cannot fly out of them at all). So I started buying up all the cloth on the AH and turning it in at the various goblin towns.
Once Ratchet opened up, that was an entire chunk of quests I could easily add in. It also opened up the two quests in Durotar (of all places) that I could grab from a goblin. I fixed Mudsprocket and got more (plus was able to fix the broken questline). I picked up a few I missed in Gadgetzan and one or two in Everlook.
After all this though, I was still stuck at 700/730.
So... more research.
A big resource that helped was going to the Wowhead.com page for this specific achievement. There were links, suggestions, and guidelines. I started using those.
First off, I hit up the items that drop that start quests. You can filter these by zone. I picked up two more quests in the Draenei islands with this. I spent a half hour killing some fast-spawning mobs in Darkshore before I gave in and assumed I'd done it in the past.
Another link in the comments brought me to a page with some "hard to find" quests. I'd done a good number of them, but found a few out of the way escort quests (the turtle in Tanaris was one).
I picked up the Dire Maul quests in Feralas and went and solo'd those. I returned at one point because a guy in the library said "Go tell So-and-so about this dead guy next to me, then come back", but it was a waste of a half hour... he just wants you to bring him a book and a diamond for a head enchant but it doesn't count.
I ran a few E'ko quests in Everlook. They don't count, but don't dismiss all repeatable quests... sometimes the first turn in does count, such as the gryphon eggs you can get in Feralas, put through the eggo-matic in Gadgetzan and get a reward. I did get credit for doing that one the first time.
I pulled up each individual dungeon in Kalimdor and found the quests for them. I found an extra Dire Maul quest I hadn't done, located the quest giver and ran it again. Sometimes quest givers in EK will send you to a dungeon in Kalimdor.
In regards to the raid quests:
* Eye of C'thun drops off the last boss in AQ40. I pugged this a few months back and won the drop. Problem is that you require Neutral Brood of Nozdormu rep. Unless you are a pre-BC raider, you will not have this reputation as it starts at hated. I ran AQ40 with some pugs and with my guild until I finally got neutral.
* I had also grinded myself almost out of hated with Brood rep on my own by killing assloads of bugs in Silithus. I had started the Scepter of the Shifting Sands questline almost two years ago when I received the Head of the Broodlord Lashlayer from Blackwing Lair. I'd solo'd my way through this. Once I hit neutral with Brood, I could move on to the next stages of the Scepter questline, which added to my quest count. Through all this, I finished the red shard (BWL run with the guild two weeks ago), and about half of both the blue and the green shards. I am currently looking for three more pages of Draconic for Dummies in the blue shard line and am at the stage to summon Eranikus in Moonglade for the green shard line. I solo'd some of these quests, the most difficult being the summoning of "Number 2" in Winterspring. I could not go toe to toe with the gorilla and wound up kiting him halfway to Everlook before he died. The rest of the questline was mostly two-manned, either me and a pally (Dr. Weevil, Chimera Lord on Isle of Dread) or me and another hunter (Fragments of the Nightmare's Corruption). One stage required six people (the 40-man raid boss in Duskwood, the Twilight Corrupter for the last Fragment). Turning in the Fragments in Moonglade brought me to #729.
* I did *not* do any of the gear turn in quests for AQ20/40. This was mostly due to running AQ prior to the achievements coming out and not realizing that these were potential quests that would count.
A few other notes:
* I would have completed this achievement three days ago likely if there wasn't a bugged questmob on Bloodmyst Isle. A demon that spawns every so often drops an item that starts a quest. I picked this up back on my Draenei when I was leveling her, but my elf was unable to get it due to the mob never spawning. This is apparently a known issue but has not yet been fixed.
* Having run alts through these areas with a leveling guide, I could remember a lot of quest hubs, drops, and out of the way quest givers. This *really* helped a lot. It's what got me the #730 quest.
* It's rare but some of the faction-only locations may offer quests to the opposite faction. Don't dismiss these. As I said, a link in the wowhead comment section indicated a goblin near Orgrimmar had been switched to neutral and two quests were now available to Alliance. A horde only questgiver in Everlook has also been changed. Don't let your past knowledge of an area narrow your view.
* Research, research. Wowhead has a lot of good information on it. Learn how to use the filters. Filter it to find drops. Filter it to find "starts quest". Filter it by zone. Make a list of the zones and go through each one.
* Some quests that are in Kalimdor but send you to EK will still count towards your Kalimdor quests. This is really noticeable when doing back and forth between goblin cities and Booty Bay.
Another thing I would also strongly suggest... DO EASTERN KINGDOMS FIRST. From what I've read, EK is easier. Plus, you may stumble across a questgiver in EK that will send you over to Kalimdor and it will give you a few that way. I did not do this and relied almost entirely on questgivers in Kalimdor (and stressed myself out far more than I should have).
* If you have pirate rep, fix your goblin rep *first*. You will not be able to reasonably finish this achievement if the goblins hate you and you have not already cleared out their quests first. If you want the pirate achievement and the loremaster, do loremaster first, then go wreck your goblin rep.
It was the "hard to find quests" list that got me the last one I needed. I deleted all the EK quests from the list and then deleted any of the Kalimdor quests I *knew* I'd done. There were a bunch listed that I wasn't sure about in Desolace so I flew over to Nigel's Landing. I found a centaur quest I could do (but did not want since it meant grinding a centaur faction out of hated into friendly), and a Maraudon quest I'd missed. I was a bit cranky that I would have to go into Mara and it would take me at least a half hour (I always get lost in there), but started heading over. But the list also mentioned a treasure chest on the coast. I remember doing it on my alts, but couldn't remember if I'd found it on my main. I headed over and nearly *freaked* when I saw the ! on my screen. Sure enough, I hadn't done it. I killed nagas and crab people for the two keys, swam over to an island, and opened up the chest for quest #730!
So, in summary... do EK first, prepare to solo dungeons, research a lot using Wowhead, look up the achievement itself in Wowhead for some great comments, and prepare to bust your ass finishing this one. I honestly do not know if I could have done it without the Scepter of the Shifting Sands raid questline TBH. Maybe if I'd done EK first? Dunno. I'm not about to try to find out. I spent last night getting 40 quests done in the human starter zone, one shotting kobolds and wolves and Defias.