It's a terrible sight isn't it? I call it the ghost navy and it caused me to stop playing Civ for months because I couldn't get the image out of my head of the zombie fleet. It's a huge vanilla bug and not a VEM problem. Lets hope and pray that G&K will greatly improve naval combat.
Could I ask one question, are you playing the game in a non-standard way? For example big map and small numbers of civs something like that? Are you playing Perfect World, some kind of map that produces difficulties for the AI to work out an attack path by sea perhaps with a complex coastline? If it's any help I play on pangaea+ and 5000BC maps to flatten the terrain a bit more to make it easier for the terrestrial AI.
It might be possible that that the AI navy bug does not manifest as much if all settings are kept absolutely standard on continents as would have been the settings the testers used when they were debugging Civ5 vanilla.
Cheers
