It's not actually "random" units: It's units that you have seen before at some point, but are now suposed to be hidden. And they don't appear at random intervals: They appear whenever one of your units moves. But I've seen this all the time myself, and highly suspect that the problem is on the game's end, as opposed to the computer's.
