I put in some changes to door placement code, which has stopped hallways from being blocked at the source. However, the general issue of existing hallways blocking where other ones need to go persists. This is an artifact of the discrete nature of the grid -- while it may be true that I have a planar graph layout, so that rooms can be connected without hallways crossing, there's nothing to guarantee that the hallways actually have enough room.
Currently I've got it taking a trial-and-error approach with different pairs of door locations for each hallway. This works out in a larger number of cases (I've had it generate reasonable levels, some of the time at least, for 5 or 6 rooms), but past a certain point of complexity it just gets stuck in a hopeless state and runs forever.
Improving on this situation is a significant challenge; I'm still thinking of what I want to try. One thought I've had is to change the A* heuristic to discourage hallways clustering around rooms. This would particularly address a situation I commonly see where a hallway wraps tightly around the perimeter of a room, blocking most possible door locations for other hallways yet to be routed. However, it's clearly a band-aid idea, and I'm not sure it wouldn't create problems when rooms are close together (currently the levels are quite spread out, another matter I hope to address in due course).
What I'd like to do more ideally is let the hallways "shove" each other around until they fit. I'd like to be able to treat the grid as a rubber sheet and just stretch out new areas when I need more room. It sounds like a good general solution, if I can manage to implement it reasonably. I expect deforming existing dungeon features without messing up structure to be pretty hairy, though. Going to ponder this one for a while.
In a way, the existing approach is a simplified rubber sheet. Having chosen a particular scaling factor and failed to lay out the level within that size, it bumps up the scaling factor and tries again until it succeeds (or enters a quagmire). At first blush it would seem that this solves the problem, albeit gracelessly, since if you expand endlessly there should eventually be a big enough gap wherever you need one. However, since it re-routes every hallway after it re-scales, the same exact situation can simply occur again because it will just hug the corners that much tighter. So, something more sophisticated is called for. I'm still convinced it's tractable, though.