The Gutter Prayer was always The Gutter Prayer (well, it started out as Nanowrino2014, but that title would never fly.)
The Shadow Saint was The Divine Machine for a very long time.
Book 3 eluded a title for a long time. Structurally, there are two plot strands: stuff’s going on in Guerdon, and at the same time Cari’s having adventures far away across the sea. The two strands come together as the book goes on, but any title would have to fit both plot lines. The working title was Anchorhold – an anchorhold is the small cell where an anchorite, a walled-up monk, dwells, which fitted the Guerdon/Spar plot, and it felt nautical enough to cover all Cari’s ocean voyaging. However, as the book’s part of a series, the title had to confirm to the format of the other books. So, THE SOMETHING SOMETHING.
I proposed a bunch of possibilities to Orbit.
THE DIVINE ANCHOR
THE BURNING SEA
THE DROWNED FIRE
THE HOLY FIRE
THE GOD PRISON
THE BROKEN WORLD
THE FALLING GOD
THE STORM PROMISE
THE BURIED FIRE
THE MARTYRED THIEF
None of them quite worked, but the Orbit team suggested combining two of them as THE BROKEN GOD. I tweaked some sections of the book, and it grew nicely into the title, and now I can’t imagine it under another name.