The Hitch-hiker's Guide to the Galaxy text adventure had what was probably the most stupidly hard puzzle in it ever. The objective was to get a Babel Fish in your ear before the Vogon guards seized you. However, holes in walls, drains, and cleaning robots all conspired to stop you.
What made it hard was not the 'how do I solve this' part, but the fact that what you needed wasn't obvious in the slightest. Like, you needed your dressing gown to block the hole in the wall, but by the time you'd gotten to that puzzle, you'd forgotten about it because you were wearing it, so it didn't show up in your inventory.
I had to resort to the hints to solve that puzzle. I'm not proud.
EDIT: Also, one of the rooms had the description 'The only exit is to the north'. So you would try to go north, and it said 'There is a wall there'. Eventually, after poking around for a while, the game would say 'We lied. The exit is east'.