When designing a game [I didn't build], I realized one of the most important ways of making the game indefinitely interestingly was to make it really hard to solve. This meant making it NP-hard on purpose.
One of the last bosses in Zelda is an interesting example. It starts as a dragon with three heads. One which is only killable by fire, the other by ice, the last one is invincible but tries to bite you. When the outer heads are dead the third head transforms to a fast moving snake which you have to hit at a specific point to damage. Each time you hit it it gets faster. Now, if you die something interesting happens: The next snake will start slower i.e. easier, so players should be able to kill more parts of it. This repeats itself every time you die. I noticed this when my mother (who loves Nintendo games, but isn't a really good player) died 20 times or so at the snake. Every time it was a bit slower and every time she was like "Well I did manage to kill one more part. THIS time I kill it!" and ran in again. In the end she killed the boss and was happy.