Yeah, that's why you add a couple that roam around the whole map. Don't know, 2-3 upscaled enemies that roam from north-west to south east and 2-3 that roam north-east to south west. If you find them and kill them next time they roam perhaps from west to east after a day or so.
Randomization or path and enemies. I don't think that would cause some major infractions in memory handling.
A random encounter would also be a nice touch when traveling through waypoints. You could add the spirit world encounter fighting spirits in a waypoint.