The thing that clicked today: I had been saying my machines could all reach each other, when what I actually knew was that the paths I happened to use every day worked.
Built / shipped
A real matrix, not a spot check. Five machines means twenty directed pairs once you exclude a machine talking to itself. Direction matters: A reaching B says nothing about B reaching A. Tested strictly, with no interactive prompts allowed and each connection made to prove which machine and which user it actually landed on, fifteen of twenty passed. I would have guessed twenty.
The gaps were not random. One machine, the storage box, had no configuration and no trust in any direction at all, so five of the five failures were the same missing setup. The remaining gap was a missing host key one way that turned out to be a missing client authorisation the other way as well.
Trust seeded only from keys I verified locally. There is a convenient command that asks a machine to state its own key, and using its output to establish trust is circular: an impostor answers that question just as confidently. So every key installed here was read off the target machine directly and matched by fingerprint. Nothing scanned was ever installed.
A staged install instead of an in-place edit. For the machine that needed everything, the new configuration and trust file were built as separate candidate files, all four outbound connections were required to pass using them, and only then were they moved into place atomically and tightened to owner-only permissions. If any connection had failed, nothing would have changed.
Problems & fixes
A repair job reported success and had actually rolled itself back. One of the automated repairs came back with a clean success message. Checking the machine directly showed the live file and its backup were byte-identical and the key it claimed to have added was absent: it had appended the key, then executed its own rollback path anyway. The report was confident and wrong. The rerun used a fresh backup and proved the result by making the connection rather than by describing it. This is the single best argument I have for verifying at the source rather than trusting a summary.
A host-key failure hid a second failure behind it. Two machines could not connect, and the obvious cause was that one did not have the other's host key. Fixing that revealed the second machine had also never authorised the first machine's current client key. One failure masked the other because the connection could not get far enough to reveal it. Trust and authorisation are two independent things and now get checked independently.
A trust file was world-writable. The storage box's known-hosts file was mode 0777, meaning anything running on that machine could rewrite what it trusts. Set to owner-only along with the new config.
Machine names and role names are not the same thing. My notes had been mixing the physical machine with the name of the job that runs on it, and a tunnel name had drifted into the node list as though it were a sixth machine. It is not a machine. Cleaning that up removed two phantom entries from the matrix.
Decisions
The storage box reaches the far machines by hopping through a nearer one rather than getting its own route to everything. Fewer direct paths to secure, and it only ever needed to reach two of them directly.
Every rollback artefact was kept in place after success, named for the job that created it. None were executed. Cheap to keep, and the one time a job misbehaved it was the reason recovery was trivial.
Learned
"It works" usually means "the paths I use work." The five failures were all in directions I never exercised by hand, which is exactly why they had been broken for an unknown length of time without my noticing.
A confident success message is not evidence. The rollback incident produced a clean report of work that had been undone moments earlier. Proof is the connection succeeding when I make it myself, from the machine in question.
Still open / next
The storage box runs a vendor OS with an older SSH, which emits a key-exchange warning on some connections. It is non-blocking and I have left it, but it is on the list for whenever that OS gets its next upgrade.
One connection to my laptop timed out during the build and passed on retry and on every rerun since. Laptops sleep, and I have not decided whether that deserves handling or just an asterisk.