As a kid, I owned Kings Quest 3 and 5 (side note, KQ5 was available on NES). Both are in the cruel category, and I never met anyone who came close to beating them. They were fun to play occasionally, but the most fun was had by showing to friends and letting them play (everyone was blown away).

Sierra operated a 1-900 tipline (cost $0.75 per minute or similar). I can't imagine anyone beating these games without those tips or tips from a magazine.