Yes, I gave up on the "The One That Got Away" yesterday. I just waited a day and did the shrimp one. Right now I've raised my fishing skill to 365. I checked E's Extreme Fishing page and decided to fish in Dragonblight per his guide. That seems to be ok. I'm getting some Pygmy Suckerfish once in a while which should sell pretty good.
Look on the map - in the lower left corner you'll see a small lake - if you've done the walrus man quests then that's the lake where all the ghosts are. There's seven or eight pools of Dragonfin fish in there - if you've managed to clear 400 skill with your cooking then use your cooking awards to buy the Blackened Dragonfin recipe (http://wow.allakhazam.com/db/item.html?witem=42999)
and cook the heck out of those suckers - they're going for around 150g a stack (although a stack takes two stacks of raw dragonfins and one stack of spices) on most servers.
As for the suckerfish - they used to be extremely high demand thanks to their rarity and the need to use them to level alchemy - not sure now since the drop rate has been changed - if you work the dragonfin pools then you'll get a suckerfish every third catch on average. Definately keep them for the AH, or, make friends with your guild's upcoming alchemists by donating them.
How far should I keep raising my skill? I'm wondering what the minimum baseline skill is to be able to fish everything in the game?
Answer is 'depends' - if you want to get the coin reward/achievement in Dalaran fishing from the fountain, then you'll definately want a maxed fishing skill - same thing if you want to catch the non-combat pet Giant Sewer Rat (http://www.warcraftpets.com/wow.pets/mammals/rodents/giant_sewer_rat.asp).
Additionally, some of the deep sea fishing off the southern coast where the iceburges are needs a rather high (400+ but don't remember exactly) skill to catch those fish and those fish are components in some of the high end cooking recipes.
Right now I'm doing ok but probably need to keep going in order to fish the pools in Dalaran. I do have a stack of the plus 100 lures, which are nice too.
If you're not in a hurry then just make fishing part of your daily routine and it'll max itself out on its own - when you're doing your dailies just pop on down to Dragonblight and just work the lake I mentioned for ten minutes or until you've got yourself a stack of Dragonfin or suckerfish or whatever short goal you want to set for yourself - that'll get you 1-3 points per run and you wont burn yourself out on fishing - win/win!
Edit - since you're in the xpac now, be sure to work your Kalu'ak rep to score yourself a http://wow.allakhazam.com/db/item.html?witem=44050;source=live
at exalted. Edited, Feb 8th 2009 7:32pm by rusttle