I was looking up a French town on Google Maps, when it struck me. There are bays shown as "Bay of ..." on the map, as well others listed as "... Bay". Their naming seems to be consistent with the naming in other maps I checked.
Likewise we have most seas listed as "... Sea" (e.g. Caribbean Sea), but some oddballs like the Sea of Okhotsk. This also can be noticed in the naming of gulfs.
I simply can't figure out the rule. Here is a link to the list of seas on Wikipedia.
(On a random note, this is probably coincidental, but the names of bays I can think of off the top of my head that end in "Bay" are all in America.)