It depends on when you want to spawn the enemies - if it's midway through a 'level' when the other entities have already moved then there's little alternative to testing as eons suggests - unless you have a spawn point (or several) that is not reused until clear, that way you just check that area rather than testing against all other enemies etc.
A simple but effective way at the start of the level: if your sprites were, say, 64x64 pixels, imagine the viewport split into 64 pixel columns (or wider) and place your enemies somewhere in that column. You might not have or want to use all the columns, adding to the apparent randomness. For example, if your viewport was 640x480 you's have 10 columns but might only want to spawn in six of them.
Just some ideas... :D