If the MapRand is not set to 0, then that's likely your problem. Set it to 0 and try again. If it -is- set to 0, then set it to a random number pulled out of thin air: something large, like five or six or eight digits. Reset it each time you want to replay on the same map script. Again, this is only meant as a temporary workaround until a more permanent solution can be found.
This issue is a bit of a head scratcher, as no sign of anything of this kind has ever showed up for me -- and still didn't in my testing just now. I've run hundreds upon hundreds of tests, including sometimes thirty in a row on identical settings, and never seen a duplicate. The random number generator is not my direct responsibility, though, so all I can do is pass on your reports.
- Sirian