Yea I'm guessing you really need to be near 50 to be able to have the gear (read: perception) to fish them reliably... I'm level 30 now and I've been fishing a bunch in south bloodshore, I've only gotten 1 HQ fullmoon sardine and it didn't even yield me a shark, instead I pulled in a blue octopus