Yes, the signing side is a client bug, and a relay cannot repair it: it has no way to know that a kind-5 carrying one e-tag was meant to kill four earlier versions of the same address. That is exactly why NIP-09 lets an a-tag delete every version up to the deletion's created_at, and only the signer can write that tag.
Two places where it lands on Nostropus anyway, and that is what I meant.
First, a correction to what I wrote earlier: a relay does not normally re-learn a note from its neighbours, relays do not crawl each other. The note comes back because a client re-publishes it — an old client with the note still in its cache, a restore from backup, or a copy tool. Which makes a copy tool the most likely re-broadcaster in this story, and the one place where the a-tag stops being a signing detail and becomes behaviour you have to build. NIP-09 already says clients SHOULD broadcast deletion requests to relays that do not have them. A copying tool is a client. If Nostropus mirrors notes onto a spare relay but leaves the tombstones behind, the copy it just made is a note the author deleted, sitting on a relay that will now answer queries for it.
Second, exactly your idea. You already walk an author's history, so you can read each kind-5 and ask whether it can work at all: only an e-tag, but the referenced kind is replaceable or addressable (0, 3, 10000-19999, 30000-39999) — that deletion is incomplete by construction and the older version keeps answering. "Incomplete deletion event" beside it, as you said, would save people an afternoon.
On caching you are right and I should have split the cases earlier: for the first seconds a stale read looks identical to a rejection. My nos.lol case was not that one — the acknowledgement came back and the event never appeared, not a minute later and not an hour later. So I now treat a first miss as unverified, retry after a gap, and only call it a rejection when it stays missing.
For retention you do not need a server. Page backwards per relay with until set to the oldest created_at you have seen so far, and record how far back each relay still answers: one REQ per page, and "this relay holds notes back to March" printed next to its name tells a newcomer more than any uptime chart. A monitor answers a different question — whether a relay responds, not what it still has.
