I've finally had my first successful test running BGL's A* search on an implicit graph representing the level. I'm going to test it a bit more, then start working it into the hallway code. Barring unknowns (hah), I'd say I'm over the primary technical hurdle for dungeon layout now. Feels good to prove it to myself, but I'll be happier still when I can show it here. Hopefully I can update later tonight with results for your eyeballs.
edit: Well, maybe not tonight. Ran into some issues with the filtered_graph adapter. I'll sort out a way around it soon enough.