Quote:
Truly, forcing people to walk is a stupid idea. Instead, give them a damn reason to go out walking.
Have some content in areas that can't be teleported to. Put content on the trains, boats, and airships (something better than just random enemy spawns, though). Put out quests that come up at random, have other quests drag you through the middle of nowhere, and then have some more quests start out there in the middle of nowhere. The caravans are really good for this, as are gathering points.
And then when they're done with all that, let them teleport the hell out of there so they can go join a raid on the new primals. >_>]
You said it best.