People are only cheating themselves out of enjoying all the game has to offer when they use it.
I agree with most of your post, but I do not understand the viewpoint that one is cheating one's self out of enjoying, when anticipated boredom is often the reason one chooses to use fast travel.
**Edit: The original Bards Tale did not have Fast travel. You had to walk everywhere in first person; and not only that... To those that want full real life immersion. Bards Tale was one up on every RPG game since! (You could be in a dungeon several floors down, and lose your torch, and not have enough magic to cast a light spell ~This meant that you had to walk back upstairs to the surface in utter (0,0,0) pitch blackness. (no auto-map either, you had to make you own ~and IMO it'd be cheating to read it when you are supposed to be in the dark).
Whether fast travel is nice or not, depends much on the game. For example, playing games like Daggerfall and Arcanum without taking advantage of fast travel would be insane and extremely time consuming.
As I recall, (not from personal experience :laugh:) its estimated to take 48 real hours to walk from coast to coast in Arcanum.
While in some other games it doesn't only save the time of the player, but also make the game noticeably easier. If you just escaped a difficult dungeon and is very low on HP, you can easily just fast travel to safety instead of carefully going back and hope you won't encounter any enemies on the way. Or if you do meet some enemy you don't want to fight, you can just run in a random direction until the enemy is far away enough and just use fast travel.
I have always considered 'fast travel' in Oblivion to be broken for this one reason. It was not like that in Fallout where you could die on the trip. (Though its true, if you managed to run away from combat, you could usually escape; and it was exploitable when you were on the edge of the map).