I don't think those games are hard at all. The solutuon is to do a Depth-first search by hand, algorithmically trying all the possible game states until you find the winning one. Thats not hard (infact it's super easy and guarantees a solution), it's just really, really horribly tedious and boring.
A pet peeve for me is platformers like those where the solution is obvious, or obvious after a handful of deaths, but the execution is hard to pull off. I'm looking at you, Super Meat Boy. I hate that game so much I played it for hours just to ride the wave of building rage and frustration. But besides SMB (wow, I just got that) being an incredible tease, requiring frame-perfect jumping when you already know the solution is a bad mechanic.
SMB is different. The fun in SMB comes not from solving the level, but from mastering the controls, along with the feedback the game gives you when you perform action (sound effects and animations are much more than a "pretty effect" in a game like this, and serve a mechanical purpose). It's fun because your brain associates the successful completion of a level with your gained skill, and rewards you for it.
When you completly master a game, it generally stops being as much fun. Someone who could beat SMB 100% of the time would probably stop being entertained by it. Many people have already mastered those sorts of text games (discovering the "try everything" solution to these games would give people a mild feeling of reward, in the same way discovering the tactic to Tic Tac Toe does, but then thats it), and thuse they are really easy and boring (but still take a long time to actually complete). At that point, there is no more "skill" to gain.
The fun in games like SMB is the overcomable difficulty executing the solution, not the discovery of the solution. The fun in a puzzle game is the discovery of the solution, not the execution (That "Eureka" moment). Those "ultra hard text games" are both trivial to solve and execute (taking a long time to execute does not make something difficult), and neither gives much of a reward for doing so.
It should also be noted that this is all based off the game mechanics of such text games. They are terrable games. Some can still be entertaining by providing entertaining text and situations. (Interestingly, a bad game can still be an entertaining product).
I think the problem for "Retro-inspired" games is one of promotion. Pixel art can look quite good (and a number of such "Retro" games have good art), but it's not really "Retro" anymore given it's quite a common art style. Pixel art can look as good as and is just as valid of an art chose as 3D, and you can pick pixel art for other reasons than "Because Retro". The problem is just abusing the word "Retro" as a "feel good" word that is designed to invoke positive emotions (be that through nostalgia or otherwise). Many of the "Retro" games I have played are debatably not even very retro, but are still fun.
Being retro doesn't make a bad game, but it doesn't make a good game either. It's just an overused marketing term.
Also, as Draxis said, like Dwarf Fortress's choice of ASCII, pixel art can ease the development process, and can be a valid design decision for development/mechanical rather than artistic reasons. I won't shy away from a game that advertises itself as "Retro", but I do wish people would abuse the term less.
Minecraft art styleMostly in reference to the player "models", and the textures. The "Blocky worlds" has some legitimate uses, simplicity of implementation, it's easy for the player to understand how their actions will affect the appearence of the world etc.
Minecraft's graphics look sort of bad, but they are functional and non-offensive enough to work. But I have seen the style pop up in other non-sandbox-construction games, and it looks terrable. If I were going to make a game that wasn't a Minecraft clone, I would not base my art style off Minecraft.