There are levels similar to "It's Hero Time" or "Just a minute", where a short time limit is actually part of the puzzle. It rules out many backroutes there, and it's the most elegant enforcement in that case.
For the levels you quoted, I'm not sure how effectively they really rule out backroutes. Just a Minute for example can still be done with one digger and one basher on the PC version, although admittedly it does require a bit of release rate jiggering. On Mac and Windows version with slower clock I don't think it even needs the fancy jiggering to work.
More importantly, while it may be elegant (or at least easy) from the level designer's perspective, I feel that using time limits to rule out a route may be the cruelest thing to do to the player, for the very same reasons you object to time limits. The player won't find out until late into his efforts, and then it may take a few retries on the blocked solution before he decides to try some other solution, if he hasn't ragequit by then.
===========
I think again, time limits work less well in Lemmings compared to more action-filled games like Mario, for the same reasons of the underlying game design. When you are in full control of a single character, have full control of its movements, and you're already amped up from the intricate monster-dodging and platform hopping, having a time limit in some levels can add to the excitement (provided it doesn't go over into "ridiculous frustration" territory). And actually it can work for some Lemmings levels like "Heaven can wait...", though perhaps less effectively. It definitely doesn't work well on levels where you already have to do a lot of planning and work to solve, and then to have it ruined at the last minute because of something silly like not releasing the crowd early enough. Although, I have to say action replays + fast forward should help there a bit.
But I'm in general agreement that the time limit is superfluous in most Lemmings levels, and if a level is already tricky to solve or execute, adding an unforgiving time limit does seem more of an overkill then anything else. Fortunately most of the official levels are pretty generous with time limits, and the selected few that aren't uses the time limit wisely and appropriately.
Unlike Lemmings, some games actually have lives, and the player loses a life when he runs out of time. This is absolutely horrible.
A lot of these designs are effectively holdover from when most games are on arcade machines that you need to feed quarters into. In that setting it makes sense why games are designed like that. And I guess old habits die hard even when it comes to game design.
Again, I think it depends on the game. I don't think I find lives and time limits much of an issue when I played Mario for example, but undoubtedly there are other games where they can be infuriating.
For a modern game, it does seem that time is typically better left as an achievement rather than a forced limit. But again, there are those occasional cases like "It's Hero Time" where it can make sense. Ultimately it's just another game design element with pros and cons that need to be carefully considered. I'm not sure there are any hard-and-fast rules to be made for this, but I think your checklist of why time limits can suck is a good checklist for every game designer to keep.