You could have always taken one of the quick-teleport portals from spawn that sent you 10,000 blocks in one of the cardinal directions. Otherwise, having to walk when you start out fresh can't be avoided: you're trying to find a place to live so you have to cover as much area as possible anyway. Once you settled, you could always just travel directly to spawn or to a friend. It wasn't entirely convenient but there was no difference between 5k blocks and 10k blocks out. I think it's a challenge, but not the right kind. Why should I have to waste more effort to travel to friend B over friend A simply because s/he lives somewhere farther?
Fair enough, but travel and the risks it posses are one of the things that make a survival server interesting. When travel is a challenge, players are encouraged to build closer to spawn, or other hubs. That leads to greater population density, and the interesting things that come with it. I'm not opposed to instantaneous travel at all, but I do think it's something players should have to work for. map pads cost ender pearls, so early on players have to be a bit careful, so they don't run out. Later, when they have the resources and power, teleporters and portals are an option.
I'm not suggesting that teleportation should be free -- just that I don't think the cost should primarily be based on distance. MapPad teleportation isn't free, but its cost isn't based on distance.
Not a good idea on alice, there's too many bags/backpacks in mods that would circumvent that kind of thing...
That's fine. IC2 teleporters already work like this. They also count each piece of armor you are wearing in the cost calc. I dislike having a static cost for something as powerful and instantaneous transport anywhere on the map, it . Add some variable or dynamic cost. Teleporting during the Day costs twice as much as Moonlight travel. Or have an upkeep associated with maintaining an active portal. Or reverse it, make the cost fairly high. Then reduce the cost for teleports to places that you frequently visit. This would make teleport hubs more viable. These are just ideas for discussion and not meant to be taken seriously.
An interesting concept is where the cost of teleporting to a certain place decreases as more people teleport to it more frequently.