If there was anything enroute when the colonies were deleted, it probably happened due to the ships creating the new colony on arrival.  That'd be my guess.

Seems reasonable enough.

It is a bug where planets get multiple colonies from one empire. Simply move everything to 1 of those colonies and then abandon the others. You can do this with ships or with SM, either works. The reason it does this is because planet and the colony are two separate entities in the code and in this case the planet was chosen the third time and the second when you invaded, you took the colony from the enemy.

I'm not sure if that's the case here, but the newest version has a bug (that wasn't present in earlier versions) that if you send a freighter or a colony ship to a planet where you don't have a colony, the game will create a new colony every time a ship arrives there.

As an example of what I mean let's say you have a planet X that is not your colony. You take a colony ship and give it a repeating order to send people there. The first time it arrives it creates a colony that is automatically added to the empire. The second time it arrives it does so again, creating a second colony on the same planet. The third time it arrives it does so again, creating a third colony on the same planet and so on and so forth. I think that's what happened here, but I cannot be sure.

To avoid the bug simply create colony first, before sanding any ships in.