"replace" the standard islands ? Why on earth for ? Whats wrong with them ?
They are perfectly fine the way they are. Maybe replace the new islands that look like the standard islands... but leave the standard islands alone <img src="style_emoticons/<#EMO_DIR#>/wink.gif" style="vertical-align:middle" emoid="

" border="0" alt="wink.gif" />
Random sea island chance:
How often do you simply press spacebar to go into blank sea? Why would you? If you add a random condition that you may find an island, then it would make people want to jump in and out in and out of sea and map, just to get a random island, because all it does it by chance show one.
That is highly unrealistic.
Possibly another approach could be that while you are sailing on worldmap, an 'island icon' pops up for a very TEENY spot on the map (maybe add the LAND HO! sound). These spots are randomly generated, and once one is 'entered', it is permanetly added a little flag point in the map (so you can return to it, since it is now charted).
There would be a max number of these for any given game of course... cause honestly, there is only a certain number of deserted islands in the caribbean <img src="style_emoticons/<#EMO_DIR#>/wink.gif" style="vertical-align:middle" emoid="

" border="0" alt="wink.gif" />
Exploring the little island, could then result in loot. Either by mooring to it and walk explore, or just a 'sail up to it, and it searches the island automatically when you try to moor' sort of action.
Likewise, those "sea battles" you come across... those could be a good spot to randomly place a small island (very small chance, but a chance nontheless). Since it would be something you jump into for a reason... and the loot on the island could be far greater, thus the battle... and you could only loot the island when all enemy ships are out of the area (just like how the moor point works now).
Your idea has serious potential for a really cool addition! <img src="style_emoticons/<#EMO_DIR#>/biggrin.gif" style="vertical-align:middle" emoid="

" border="0" alt="biggrin.gif" />