I spent 45 minutes fishing in Sarith: 0 Prawns
I spent 45 minutes fishing in Rubak: 0 Prawns
I spent 30 minutes fishing the pond north of port-in in Dragonscale Hills: 39 Prawns
If they can be fished in VoA zones, they must be exceedingly rare. I caught a TON of Raxil Fish (I had to buy another freezer to store them all) and a meager amount of Oseka's Messengers.