You are in the third world right? You need to be in the third world.

I stayed as close as I could to where the Sunken Tower was and moved one up, one down, and up and down and so on and so on.

I got lucky and found him after 10 mins, but I hear it could take quite some time.

Remember that you're looking for a man bat named 'stingray', not actually a stingray. Make sure you check the names carefully (which I'm sure you did).