For what it's worth, I discovered all of the last 6 zones using my sub with all shark parts. It didn't take more than 4 trips for any of them.

It's pure rng.