We were closing in on doing WoF when we realized that none of us in a multiplayer game (why is "multiplayer" not a recognized word on a gaming site?) had looted any chests in the ocean. We all assumed one of the other players got there first.

Where do you get flippers from? I've resigned myself to opening chests to get Sailfish boots, because there evidently are no Flurry or Hermes Boots in multiplayer, (at least, none of us have found any yet, and we've mapped out most of the sub-surface) but, jeez, Water Chests outside the ocean are pretty hard to find. Even with the Metal Detector...

Water Chests will usually spawn if a chest is to be spawned under naturally occuring water, regardless of biome.

http://terraria.gamepedia.com/Water_Chest

So have you encountered a situation where there are sizable oceans, and exactly no water chests in them?

I generated several single player maps, they all had them. I've generated 4 multiplayer maps, joined with a pre-hardmode character, (just in case that might be a problem) and there were none in the ocean on any of them.

Yep. The RNG isn't Nintendo bad, but sometimes it slaps you in the face.