The solution I had in mind was proving to be too complicated, but here is another solution that doesn't use any third party plugins.
http://dl.dropbox.com/u/5426011/examples16/inf_map3.capx
The idea is save a bunch of random numbers in a big array at the start of the layout. Then using an formula like Array.At((x*23+y*5)%Array.Width) you can get a random number for any position on the layout. The 23 and 5 are arbitrary and can be any value.
The main drawback is this method does create a pattern that is noticeable when the array is small.