A detailed debugging dive on a 4-room layout revealed what I hope is the primary problem with hall layout: doors are being placed too close together. Nothing surprising about this, in retrospect; the doors are being placed along the line segment connecting the two rooms' centers, which by no means guarantees doors won't be adjacent (actually, they could probably even wind up on the same tile, in theory). Since the layout algorithm forbids running hallways through any point adjacent to an existing open space (such as another hallway), an adjacent door with a hall leading out of it makes the new hallway a non-starter.
So, it's time for a new theory. I'm now pursuing an approach that seeks to space the doors out evenly along the room perimeter, then assign each door position to the most suitable hallway. Iterating around the edge of a room should be a fun little coding exercise, and I'm hopeful that the extra space will give the multiple A* calls enough elbow room to work their magic.
More, as always, when I have further results.
Oh, a couple bonus items. I found this interesting article about a particularly twisty hand-designed dungeon map, containing a number of Escher-inspired twists and bits of impossible topology. I've had numerous ponderings of putting similar areas into SnargleQuest (to make it all the more snargly), so this is excellent food for thought. I recommend a proper look at the PDF itself, for details on the areas of interest.
Secondly, I managed to find an online copy of the pen & paper RPG Lost Souls, which I'm happy to see is now under the Creative Commons license. Page 64 has the table at the core of the skill system, which as I've mentioned before has heavily influenced my own approach to handling skills.