It seems there should be a practical limit to the size of a re-org - I mean a practical limit that is smaller than the current height. Vincent's proposal suggests that a year's worth of blocks is such a practical limit. I agree. There are probably lower limits that are practical too, but I like an entire year just to be conservative. As Vincent points out, "An attacker will need to have hidden hashing power to overwrite a years worth of blocks."
TL;DR for the rest of this: Txns that lose confirmations from a reorg and then show up in the mempool but not in any of the next few blocks indicate malicious mining.
I see a blind spot here. We are seeing the rule that says the longest chain is the valid chain as impossible to break, but it isn't. We broke it to fix the BerkelyDB problem. The code itself would have prevented us from doing that IF 51% of the hashpower had been used to build on the wrong chain, but it wasn't.
Justus' question about what malicious means is key here. The blind spot is a bit more complex than just viewing the longest chain as impossible to break except with more than 51% of the hash power. The blind spot is our inability to distinguish between malicious blocks and honest blocks.
Rune suggests that empty blocks indicate malice. I like that (which is why I advocate using BitcoinDaysDestroyed to decide between blocks at the same height that appear at nearly the same time, rather than first-seen). There are other methods we can use to distinguish between malicious blocks and honest ones. I'm inventing one right now, but I'm sure better ones can be found.
Here's mine: Once a transaction has been confirmed, its originator generally takes on the responsibility of re-broadcasting it if it gets re-org'd out of its confirmation(s). Many mempools will see that re-broadcast,
if it happens. Any malice in a 51% attack would come in the form of failing to include such transactions. If we have a history of orphaned blocks, then we can check to see which ones have been included in non-orphaned blocks since they got reorg'd out. Such transactions should be top-priority after a reorg, even if they have zero fees. When there is a transaction that doesn't appear in a new block within a couple hours of a reorg, that indicates dishonesty, usually in the sender (but that could be negligence), but possibly in the miner. Looking at the mempool would determine which, wouldn't it?