To me a challenging game requires skill but contains enough equalizers/randomness that even a master will have trouble beating the game more often than not. It is what keeps EMs perpetually interesting, and is also one of the accolades of IM. In other words, goals don't have to be deep for a game to be challenging.

Deep rulesets provide a different set of challenges... a bad player simply can't shoot well enough or keep balls in play long enough to get to Valinor on LOTR, but it provides a consistent challenge to seasoned players. I hear a consistent theme about LOTR that people tend to play it less in their homes because it requires you to devote time to a single game, but when you have the time, the rules flow like no other. SM is similar in that respect.

I also agree with your inclusion of Black Hole in the discussion, it is one of the reasons it has lasted in my collection.