I think it's visually apparent in Bowser's Castle when you've made progress vs. being sent back, which is kind of similar to some of the earlier maze fortresses like the first fortress in World 3. There are other levels that have doors or pipes that either do or don't send you somewhere useful.
But solving any of these mazes without a strategy guide will probably call for multiple lives because you almost certainly won't be able to find the complete solution in a single run-through. I think that's characteristic of many Super Mario 3 levels, though, because pipes and doors that send you backwards aren't that uncommon.
Other examples of tricky maze levels where you have to explore a lot:
6-5 (you have to fly while holding a Koopa shell in a place where it's not particularly obvious)
7 first fortress (again, you have to fly in one particular place in order to escape)
8 fortress (lots of backtracking, several different ways to solve it)
Edit: I didn't realize that when you said "the original" you were referring to Super Mario Bros. rather than Super Mario 3. I agree that 8-4 in the original Super Mario Bros. is a huge nuisance to figure out although I think you can get it with a degree of discipline, probably in only 1-3 lives. If I remember correctly, there are three branching points where you have to repeatedly choose passageways and you can be sent back if you chose the wrong one. I think the hardest branching point gives either 8 or 9 total possibilities, of which only one is correct.