On maps with a large number of worm holes (such as Ancient Gifts) the AI will not always find out where a worm hole goes to, so if the only way to your home planet is through a worm hole they will not be able to send envoys or any other ship there.  This is especially problematic when you are on teams at the beginning of the game because the player does all of the exploring and the AI does not know where the worm hole goes, but they know where each end of the worm hole is located.

I think the easiest way to fix this would be to have the scout's explore ability to check if their owner knows where the worm hole goes to, and if they do not travel through it.  The scout's should do this check even if their owner knows where both ends of the worm hole are.

Another fix could be if you have a ship vision pack with another player you gain the knowledge of where a worm hole goes when one of their ships travel through it.

A suggestion I just thought of would be to allow players to trade maps which would contain all of the information about the gravity wells that the player has visited.  The map would contain the information that the original owner knew about the planets in it.