While it is nice flavour-wise to imagine a 'nice slow world' that has no fast-travel magic available, I'm not sure how you would provide a fun high-level game in it.
Saeviomagy has asked the right question:
What types of high-level challenges are there that not allowing fast-travel magic would make possible, or make more interesting? Two types of high-level scenarios have been mentioned in this thread that I can remember off the top of my head. I can't see how nixing fast travel would be a benefit for running/playing in them.
1. Large-scale power play:
As WizarDru has pointed out, his low-epic party is dealing with nations, curches and rulers. I can't begin to imagine how this should work without having fast-travel magic available. At some point the PCs are going to outgrow their local rulers, and indeed most rulers or powerful PCs on the continent, or planet. How are they going to expand their area of operations without fast travel? In the modern world we board a plane. In a fantasy world, we Wind Walk, Teleport, Transport via Plants.
I can see dropping the bland Teleport for the more flavourful alternatives like Wind Walk, Transport via Plants, Phantom Steed, I can see replacing it by new fancy things like Falling Star (fast-travellling in meteroid form, a Midnight netbook spell AIR). I can see putting all sorts of restrictions on fast-travel magic to make it less prevalent. What I find difficult to imagine is how you would do without having fast-travel magic at all.
2. Dungeon crawls:
We can probably agree that Climbing, Jumping and crawling your way through a dungeon isn't the way to challenge a high-level party. Unless you've banned all the low-level utility spells like Fly, Levitate, Polymorph, Spider Climb and Gaseous Form as well, are not allowing the Druid to Wildshape, and no one can summon things that will carry or tunnel you out of there.
If we want to prevent a party from accessing/leaving a dungeon location too easily or quickly, we can work with the traditional special defences for the location, whether man-made or natural - no need to get rid of the entire set of fast-travel magic to provide a specific challenge for a specific location.
So where is the benefit of nixing fast travel in a high-level game?

Can you think of any?