I'd have to say the worst time I had with a puzzle was the resonance puzzle in Myst IV.
Spoiler:I missed one of the clues somehow, a piece of paper lying on the floor. It made a nearly impossible task, well, impossible
Countless hours were spent trying to figure that out, finally stumbled across my mistake, which helped, but it still took awhile to get it right..