Regarding the apparent transport starvation, it appears that a couple of things might be going wrong. In CvPlayer.cpp, CvPlayer::doTurnUnits() has a bunch of code to make sure that each player has at least one ship. However, this code does not guarantee that said ship is a transport. It won't gift ships that can't be bought in Europe (i.e. Coastal Trader), and it will find the lowest cost ship (which should always be a Caravel-equivalent, don't make other ships cost less than Caravels or this will break!) However, there's nothing in the bHasShip code (beginning line 2334) that guarantees that when deciding if the player has any ships, the ship found is a transport. All it's doing is checking DOMAIN_SEA, which would be matched by Coastal Traders, Sloops, and other warships.
I suspect that this code might well trap an AI who loses his last transport but has a non-transport ship and low gold. He won't be gifted a fresh transport, and he will never get the money to buy one because he can't trade with Europe. Unless he scouts or trades with the natives to get cash, he's stuck. (Some AIs don't seem to trade much with the natives, and it seems that the AIs are not doing land scouting properly in 0.04e.)
This problem in the C++ logic would probably have been masked when there were no Coastal Traders and no Sloops. With no non-transport less than 3000 gold, it would have been unusual for the AI to wind up stuck with no transport in the early game. Later on, the likelihood of losing all transports at once would have been low, and the AI does seem to try to keep at least two transports once its economy is large enough.
So, what's the answer? It would be easy enough to patch the bHasShips code to check only for transports, and to make sure that eCheapestShip can only be a transport, so that the AI (or the player) never gets wedged by transport starvation without the King coming to the rescue. I've never yet compiled a CvGameCoreDLL, but if it can be done with MinGW I'll give it a try (I'm an Open Source programmer, I don't own a copy of Visual Studio.) Unless someone thinks there's a better idea?