several random spawns/patrol patterns for the enemy would help.

the naval strategy game Fleet Command uses this and just about every time you play a level it seems teh ships and their locations are different.