My vote for the most irritating quest is "Deep Ocean, Vast Sea" in Darkshore. First, I hate fighting in the water...battle in a 3D environment just doesn't work as well in WoW as it does on land (a more 2D environment). Plus it's a quest done in the teen levels where most players are still getting used to their new character and skills. Add to that the fact that the quest rewards suck and you have a quest that begs to be abandoned.
Another vote would be the druid Sea Lion form quest. I swam around for ages looking for the second half of the pendant off the coast of Westfall. I finally had to look online for help.
What's your vote for the most frustrating quest in the game?