I have some experience in procedural generation, and I think the most important question is: "How would you go about generating one of these levels if I had to do it by hand?". After this exercise in introspection, you go and try to implement it.
Most of the time, the problem of designing something can be broken down into smaller problems, which organizes the design process in a top-down manner (first subdividing a city into neighborhoods and avenues that separate them, then a neighborhood into sections and important streets, then sections into blocks and streets, blocks into buildings...).
The level in your example doesn't seem to have any overarching design, just some local rules of each room matching the adjacent rooms. This is probably a missed opportunity to give some coherence to the whole (wouldn't it be nice to have a section where a main hall gives access to several rooms, acting as a hub? How about having some section with symmetry?). The architect Christopher Alexander wrote a lot about the types of patterns that show up in buildings, and using some of his philosophy makes procedural designs much more believable.
But, if you don't want any overarching design, a randomized depth-first search will probably work just fine.
Edited by Álvaro, 08 October 2013 - 07:59 AM.