I've been meaning to play with that algorithm for a while. This may be a good opportunity to experiment with it. Handcrafting hundreds of rooms one at a time is such a pain 
Notably, the description assumes nothing about the actual content of the room. You could create a generator to fill the rooms with whatever is needed, or hand-craft room templates to match every possible scenario and just slot them in to the appropriate points. The main point here is to ensure that progress is gated with key/locks of some kind (actual keys, bombs, tools, etc), and that the player is able to (eventually) path through the level to the goal (by not putting a key behind it's lock!).
I liked the idea of taking a genetic algorithms approach--generate levels based off of a set of parameters ("chromosomes"). Harder levels would be created by assigning a high mate probability to levels the player has difficulty beating. Unfortunately, I don't think it would work well unless I had some sort of server that multiple players could contribute data to. I don't think data from just one player would be enough.
Yeah, doing "fitness" tests can be trained and are very interesting. It reminds me of the game Warning Forever; each time you beat the boss it adapts to your technique used. That's the primary challenge, in fact, adapting to the boss' adaptations.
You have to be careful about that also though, as the players that train the algorithm are the ones that it will cater to. My daughters have a very different playing style and skill level than I do, for example.