[Chris]

It's strange, it couldnt be coincidence.

When you restart, do you hit the restart button? Or do you close the Wc3 and then retest the map?
What you could also do is this:

Have an integer variable and random a number between like 1 and 4. And another one to track the number of times this function is called.
Have 4 Regions or "Zones" as ninja said splitting the map into 4 parts.
If say 1 was drawn, create a scout tower at a random location at Region1. And do it as many times as
necessary. Adding 1 to the flag each time till a number is met (like check for calls < 15 or something).

The problem is, you might be using that playable map area spot.

Try that and see if it works. I know it works cause one campaign I have does this with a certian quest. It involved finding an item but it was never in the same spot each playthrough. This is my theory on how it was done. And I wish I could supply you with triggers and conditions, but I have a hard time piecing them together, even though I can do it logically.