Frustration with "stitch" map generator...

As I continue work on iteration 8 when I get a chance, I'm becoming somewhat frustrated with my "stitch" map generator. To understand my frustration, here is the 10000ft view of how it works.

A graph of "nodes" is created, using probabilities from a map. That graph is dropped one node at a time onto a large "map", with the nodes next to each other in the graph next to each other. "Dropping" a node involved looking up one of multiple templates from a text file of that type, and placing it so the seams line up. If a node can't be dropped, we add it to a list of nodes we can drop later if we run into a room that doesn't have an output assigned. There is come complicated logic to prevent us from dropping a long group of halls and then being unable to place the endpoint room from leaving the hall. Once we have the graph generated into rooms, the map is "trimmed" so it isn't larger than it needs to be, checked for connectivity, and in/out stairs are placed.

The flaw in the system that keeps biting me over and over again is the separation between the "graph" and the actual map. It makes some things that you'd think were easy, such as dropping doors between rooms difficult. The latest thing I was trying to fix was the fact that the map looked like a spreading tree (since it was). Once you went down a hallway, you'd never reach any of the rooms in any of the other hallways. My idea was to patch this by finding empty "seams" in rooms and trying to draw hallways between them if possible. After burning an hour, I'm frustrated since by the time I've reached the hallway placement stage, I've lost all the information on the map structure and which nodes I'm working on.

I've booted the feature to iteration 9, and in that I'll decide if I want to refactor this map generation to something easier to work with or rewrite it new. Does anyone have any references to map generators that produce great looking maps with hallways, rooms, and such?