I found a very nice list of hard-to-find quests in WoW here, but I decided it could use a face lift. So I reformatted it into a much more usable guide. Currently this is for Alliance only (though a few of the quests can be done by Horde).
The list itself belongs to the original poster.
As of Cataclysm, the vast majority of these quests don't exist anymore. Sorry!
Kalimdor Eastern Kingdoms- Teldrassil
- Darkshore
- Ashenvale
- Stonetalon Mountains
- Desolace
- Barrens
- Dustwallow Marsh
- Thousand Needles
- Feralas
- Un'goro
- Azshara
- Silithus
- Tanaris
Darkshore
One Shot, One KillIn the hills in the far south of Darkshore. (NOTE: the time between waves is REALLY long (like two minutes) and you have to wait a minute after killing the named mob before getting credit. Just be patient.
Ashenvale
The Howling ValeThis long questline that starts in Ashenvale leads to Darkshire and explains the Worgen there.
Stonetalon Mountains
Ziz Fizzik's questsIn a hut SW of Windshear Crag
Gerenzo's OrdersOff the road, above Ziz Fizzik's hut
Desolace
Claim Rackmore's Treasure!Starts at a book among some wreckage on the shore, next to a chest for an Alliance quest
Azore Aldamort's questsJust north of tower overlooking the ocean. Aside from 1 BFD quest, the only Argent Dawn rep before level 50.
Gizelton CaravanThis is a quest to escort a caravan along the road. You can do this quest 3 times at 3 different spots along the road. His bots (http://thottbot.com/?n=94036 http://thottbot.com/?n=95337) also sell some hard to find recipes between escorts.
Galen's EscapeHe is in a cage on the east side of the hostile Draenai camp.
Get Me Out of Here!She is in a basket next to a tent in north part of Maraudon camp.
Ghost-o-plasm Round UpGood to do while doing the SM prep quest.
The Pariahs InstructionsHe wanders south of Mannoroc Coven.
Shadowshard FragmentsStarts at the top of the tower in Theramore for Alliance (If you don't see Tervosh there, wait a few minutes, he should be back soon).
Dustwallow Marsh
'Swamp Eye' Jarl's questsHis house is a on the right side of road a ways out of Theramore. Bring 3 soothing spices with you.
Stinky's EscapeEscort quest, north of North Point Tower.
The Orc ReportStarts from grave next to 'Swamp Eye' Jarl'.
Thousand Needles
Lonebrow's JournalStarts at a book in the hand of a corpse near the bottom of The Lift. Leads to Razorfen Kraul.
Feralas
Doling JusticeAKA 'The Sprite Darter Quest' The elves are on a ledge west of the darter cage. When the quest dead-ends, return to the elves.
The Giant GuardianLeads to an escort quest. Take her straight east to the road, then follow the road down then back west to the quest end.
Un'goro
Williden's JournalStarts from a book that drops off just about any creature in Un'Goro.
It's a Secret to EverybodyAKA 'The Zelda Quest' Starts at a wrecked boat not far from Un'Goro entrance. Very long questline.
Finding the SourceStarts at a goblin on the west side of Un'Goro
Azshara
Kim'jael Indeed!He is at the top of a large hill in northern Azshara, near a satyr camp.
Stormers and RumblersQuestline starts from a water elemental lord on an island in SE Azshara. It eventually leads to Molten Core. There are faction requirements for some of the quests.
Silithus
Brann Bronzebeard's Lost LetterLetter drops off any of the bugs in Silithus, including the non-elites from killing the druids. Easy 8300 exp if you aren't 60 yet.
Tanaris
Ship SchedulesStarts from item from the footlockers that drop off pirates.
Tooga's QuestEscort quest. He wanders around SW Tanaris. He follows you, so you can mount up and lead him fairly fast across the desert. Just be sure to not get too far ahead.
- Western Plaguelands
- Eastern Plaguelands
- Alterac Mountains
- Hillsbrad Foothills
- Arathi Highlands
- Wetlands
- Loch Modan
- Dun Morogh
- Badlands
- Searing Gorge
- Burning Steppes
- Elwynn Forest
- Redridge Mountains
- Westfall
- Duskwood
- Swamp of Sorrows
- Blasted Lands
- Stranglethorn Vale
Western Plaguelands
Better Late Than NeverStarts in the Felstone farmhouse.
The Wildlife Suffers, TooStarts at a dying Tauran in a house at Writhing Haunt Farm
Mrs. Dalson's DiaryStarts at a book on the floor of the Dalson barn.
Unfinished BusinessShe is down a gully east of the lumber mill in north WPL
Mrs. Dalson's DiaryStart by clicking on a diary on the floor of a barn
Eastern Plaguelands
The Lost Tablets of MosharuIts a follow up to the Hakkar egg quest in Sunken Temple, you get it from a dwarf in Steamwheedle, it leads to EPL for 2 tablets, then back to steamwheedle, then the next quest goes to LBRS (can only be done 5-man), then talk to a troll nearish the dwarf to get a nice cloak reward.
Augustus' Receipt BookStarts in a house in Terrordale. Same house as Egan.
Tirion Fordring's questsHe is next to the river on the northern west side of EPL. Long questline, eventually leads to Stratholme and beyond. Nice rewards.
Alterac Mountains
Foreboding Plans2 quests Start at documents on a table in the Syndicate camp north of Tarren Mill. Min level 27.
Arathi Highlands
Crystal in the MountainsNecklace drops off level 30-40 creatures all over. The necklace is wearable and you get to keep it after doing the quest, though it has no vendor value.
Pirate Cove questsSeveral quests hidden back in this cove. You can see the boat when you fly north to Southshore.
Sully Balloo's LetterAKA 'That letter under the Thandol Span'
Wetlands
James HyalAKA 'Dustwallow Marsh Inn for alliance'
MacKreel's MoonshineAKA 'That quest out on the Thandol Span that's a pain in the butt to get to'
Loch Modan
Farstrider Lodge quests4 quests. Including 2 of the few timed quests in the game. Plenty of time unless there is competition.
Dun Morogh
Hurley BlackbreathStarts in Kharanos, and an optional pre-quest in Blasted Lands
Tundra MacGrann's Lost StashClimb the hill opposite of the yeti's cave to find the quest.
Grime-Encrusted RingRandom drop off any of the dwarves.
Badlands
A Sign of HopeStarts from a piece of paper on the ground at Hammertoe's Digsite in Badlands, long questline, leads to Uldaman.
Searing Gorge
Caught!Starts at an outhouse in SE Searing Gorge
The Key to FreedomSearing Gorge outhouse quest
The Horn of the BeastAKA 'The Key to SG Quest' Kill a dino in a cave in SE corner to start quest
Suntara StonesEscort quest starts in pit near the outhouse. Don't forget to pick up the note at end of escort.
Burning Steppes
A Taste of FlamesCan use the molt from the main Searing Gorge quest, or he will summon a drake to be killed.
Elwynn Forest
Mazen's BehestStarts near Stockades, leads to Swamp of Sorrows.
In Search of The TempleThis questline starts in the bar in the Dwarven district of Stormwind and eventually leads to Sunken Temple.
A Meal Served ColdStarts at the inn in the mage quarter. Has a timer, but it can be bypassed easily.
Feast At The Blue RecluseA follow up to Stinky's Escape.
Harlan Needs a ResupplyStarts from a man that wanders around the trade district.
The CollectorGold Pickup Schedule drops off the Riverpaws in Elwynn
Redridge Mountains
Missing in ActionAn escort quest that starts deep inside the orc champion cave
Theocritus' RetrievalA dropped item that starts a questline
Westfall
Captain Sander's Treasure MapStarts from a map that drops from murlocs
Captain Grayson's questsHe is at the lighthouse in southwestern Westfall
Sweet AmberSemi-long questline that ends with a trinket reward. Starts at dwarf in mountains of southern Westfall.
Furlbrows DeedItem drops off defias in Elwynn and leads to Westfall
CluckFind a Westfall chicken, then /cluck at it till it talks to you. No, no, you don't look silly...
Red Silk BandanasThere are several bandana quests, but most people miss this one that starts at the top of the westfall tower
Duskwood
The Weathered GraveStarts at a grave between the hermit and Sven's camp, outside the graveyard.
Seasoned Wolf KabobsRequires Journeyman Cooking to get the quest
An Old History BookDropped by most undead, ogres & worgen.
Swamp of Sorrows
Magtoor's questsHe has a quest, and also a wandering creature drops an item that leads to him.
Essence of EranikusStarts after killing the final boss dragon in Sunken Temple. Goes several steps, then questline dead-ends.
The Lost SuppliesRepeatable quest to get Stormwind rep.
Watcher Biggs' questsSouth of the road before you get to Blasted Lands.
Jammal'an the ProphetStarts at Atal'ai Exile in Shadra'Alor in Hinterlands and goes to Sunken Temple
Blasted Lands
You are Rahk'likh, DemonFor Alliance starts at top of Nethergarde tower. For Horde starts at Swamp of Sorrows, Blasted Lands border. Very long questline.
Stranglethorn Vale
Jungle SecretsThis quest starts across the road from the northern STV graveyard. You need to be there when the alliance guard gets attacked.
Cortellos RiddleStarts from a scroll picked up in the ships off the southern tip of STV. It can be in any of the 3 ships.
Message in a BottleOpen bottles on beach east of Booty bay till you find quest, then swim over to the island.
The Monogrammed SashKill the screaming giant on the island with the huge goblin statue on it. You will get the item to start this quest.
Nat's Measuring TapeStarts from clicking on a battered tackle box