Yeah, so I found a really obvious solution to the stair problem that I should have seen ages ago...
Spiral staircases! They just go directly up or down. That way corridors can't intersect them. Duh.
Good news though is that in trying to fix it, the algorithm is now as sleek as ever and much smaller than it was.
In short, it now generates a dungeon with up to 25,000 segments in arouuuuunnnnd 4 seconds.