I have been fishing at 55.2,61.9 in Bay of Storms, Azshara.

Here is what I have got, stats from fishing buddy (currently 75 catches)

Darkclaw Lobster 41 (54.7%)
Summer Bass 19 (25.3%)
Large Mightfish 6 (8%)
Stonescale Eel 4 (5.3%)
Big-mouth Clam 4 (5.3%)
Heavy Crate 1 (1.3%)

Hope that helps with some better info in how rare the Large Mightfish are. While I was fishing I had my skill around 475 (with lures etc.)

-selectrum

I've been pushing the professions and, as a result, my Lvl 38 Warrior was 295 cooking and 286 fishing. I needed those Largeclaw Lobsters and Large Raw Mightfish. But, how to survive travel to The Bay of Storms?
From Ashenvale I swam downriver to Durator,crossed over the north end to Azshara, and walked up the Eastern Coast. At the southern tip of the crescent that forms the Bay there was a pass that was Monster free and led to the South End of Bay of Storms.
I was trying to Island hop to 69,67 but was attacked by a 3 headed sea monster that conned "???"! I just managed to outrun him, when one of those giants jumped on me! I was a goner.
Luckily, I died at the approach to an Island at 79,73 inhabited by Duke Hydraxis, who conned green. Moreover, the island is surrounded by his bodyguards. So, after ressurection and and buffing up (+5 rod, +2 gloves, and +100 lure x2)I caught 23 Darkclaw Lobster and 16 Large Raw Mightfish, increasing fishing from 286 to 294!
I Hearthstoned back to Stormwind and Cooked till the 300 Level was attained. Alternate got me the Zangarmarsh Books, but I don't see how I can continue levelling until my Warrior reaches Lvl 45. Guess I'll go Prospecting.

Found the Large Raw Mightfish @ 69,67 Bay of Storms.

Went in with 270 fishing and added a 75 lure + 25 from my extreme angler - total 370!

Took my skill all the way to 300 in about 1:30 hr and caught:

-16 Large Raw Mightfish
-46 Darkclaw Lobsters

Also:

-33 Stonescale Eel
-2 Reinforced Locked Chests
-19 Zesty Clam
-1 Mithrill Casing (from a box)
-1 Golden Pearl (from a Big Mouth Clam)

Others which I had to trash from lack of room....

Just fished a small amount, along Darkclaw Lobsters and other odd things like a Winter Squid, many Stonescale Eels and a Reinforced Locked Chest at 56,52, on a small rock in Hetaera's Clutch.
Had 296+75+25 Fishing, nice catch rate, few misses :D
The right place to reach 300 cooking and fishing :D


Edited, Jan 5th 2008 9:24pm by MAOraNza

I've only gor a fishing skill of 330 and I catch them all the time of the south coast at Stranglethorn in the Southern Ocean.

Here's the link to the seller/price of this recipe.

Edited, Feb 10th 2007 1:09pm by Oborozukuyo

I fish at Hetaeras Cluch in Azshara get 1 out of 8 catchs

I get them at a rate of 1 in 25 fish in the Bay of Storms. With enhancements, my skill is 405 and some fish still get away. It may be rare for you because your skill is not high enough.

These things must be REALLY rare, havnt found one yet in any of these places