To me, it depends more on how much the game rewards players for eschewing fast travel. I always like to have the option, but it's up to the developers to keep the travelling portions fresh and interesting. To my mind, one thing a videogame should never be is tedious - fast travel exists to cut out tedium. If you can remove or minimize the tedium of back-tracking through areas you've already seen tons of times, then you've already gone a fair ways towards making fast travel superfluous.
To me, fast travel is like the narrator of a story or the GM of a tabletop game saying "you went to your destination and nothing interesting happened." So it's great for areas where you know nothing interesting is going to happen anymore. Obviously, I'll physically walk to places I haven't explored yet or if there's still a lot of fog of war on the map in an area - and even after I've already made a trek out somewhere once or twice it's often still worth checking back to see if there's anything I missed the first two times. After that, it's time for me to start fast-traveling if I'm going that way again.
There are games where I don't feel the need to fast travel, though - where the gameplay provides enough entertainment and there's enough emergent and procedural gameplay along the traveling portions to keep me entertained at least through most of the game. I still think Red Dead Redemption did the best with this of any game I've played:
You had your standard fast-travel where you could "make camp" and then go to any location on the map, so long as it was a discovered location. You could also take a carriage to anywhere on the map you wanted so long as you could make it one of their set locations. And you could also take a train which would fast-travel you along the rail route and stop at it's stations.
The other nice thing about the transport options was that you could "fast forward" the traveling so that you instantly fast-traveled, or you could also just sit back and enjoy the scenery as the transport took you to the destination. I don't think graphics always matter, but in this case it kind of does - you're less likely to "fast forward" at a time like that if the scenery is pretty enough to keep you entertained. When I played that game I often enjoyed just taking a train ride for the fun of it.
But even more importantly you could simply take your horse and physically travel the regular way. A mount gives you a means to travel more quickly and cut down on travel time, obviously, and again if the scenery is interesting enough then that itself can be a good way to encourage players to avoid fast-travel. Even more importantly than that, you had gameplay reasons to go out and physically trek from place to place, even if they were routes you'd already grown used to. For one, there were the random encounters to keep things interesting - eventually you get to a point where you've seen all those events but you can always have more and varied ones. For another you did have lots of collection side-quests to complete if you really wanted to get everything in the game.
I found the easiest way to collect all those flowers and animals and other miscellaneous stuff out in the game was just to ride everywhere I was going - just by not fast-traveling I was able to keep an eye out for the flowers I would need or find the animals I needed to hunt. And I got a pretty good idea of the lay of the land from all that riding around, which made it easier for me to spot the landmarks I'd need to keep an eye out for when it came time to track down the treasure locations.
I also very rarely fast-travel in the Assassin's Creed games for similar reasons. For one, I find it very immersive to just spend time being in the world and enjoying the sights as I simply walk around the city trying to blend in and not raise undue attention. For another there's always collection stuff and secrets to find, and an easy way to run into those is to just take your time and pay attention - I've found more flags and nodes and whatever in those games simply by walking around between destinations and keeping my eyes open than anything else.
So in short I don't think fast-travel actually undermines important parts of the game - it's something that players will use when an area has nothing further to offer them. I've used fast-travel extensively in Fallout 3 and New Vegas, but also managed to explore and find 100% of the locations on the map, including the hidden locations (admittedly, some of those required use of the guide...)
But I also fully endorse game mechanics that make fast-travel less tempting. That requires "immersive" environments that themselves are enjoyable to visit, random encounters to keep things fresh and interesting, and in-game reasons to continue to explore areas and search for things you may have missed (collection quests being the obvious solution there, but there's always more than one way to skin a cat.)