Maybe there could be a few portals of some type throughout the mud where you could travel to another mud area. It could be faster than taking a ship, but maybe cost gold or even xp to use it. Or, have some sort of gate skill which will allow you to transport to a particular area (besides recall).

Yep. All of it on my uber list of things to do