As it stands the only evac shelters you can spawn in are taken from the initial overmap only and not new overmap generated from exploring.
This has been discussed in this http://smf.cataclysmdda.com/index.php?topic=7432.0 thread over in general gameplay.