Would it be possible to use mirror images of the maps?
If so it would provide some variety, without too much extra work. A mirror image of a map could be used 50% of the time.
Also can maps be attached to each other? A series could be made which could be put together in a different order each time, so long as all the edges match up!