It works! Here's a screenshot of the first level generated with A* hallway pathing:
It's not picture-perfect yet, but the laundry list to get it there is short now that the core is working. I need to filter the grid graph used in search so that only orthogonal edges are used (to prevent those ugly diagonal hallways), and further to prevent pathing through squares with open neighbors (creating pervasive "leaks" in the level structure). Oh, and I need to rewrite the coordinate scaling code so the level doesn't have that weird skewed look. I've already got working code to do the orthogonality part, so we really are almost there.