IANAL, but the approach I'd consider is fraud/breach of contract. The previous victims settled and paid a royalty to use a patentable technology. It turns out that it was not what was represented. Ergo, refund. How it plays out surely depends a lot on regional courts, precedents, etc.

Be interesting to see how the courts would react to that though, and if they see it as a sign you are negotiating in bad faith.

The consequence would obviously be that all the licensees of a patent that has any chance of being invalid would subsequently try to get it invalidated so they can get their money back, but isn't that the intended result?

That's not what ex post facto means. An ex post facto law is a law criminalizing an act or increasing criminal penalties after an offense occurred. It does not prevent retroactive civil liability.

The more applicable concepts here are the binding nature of contracts (which settlements are) and res judicata (which means that, in short, once a court judgement has been entered and made final, a party cannot relitigate it to get a better outcome.)

You can put such terms inside your own settlement agreements. One common way is to use a running royalty rather than a lump sum royalty. If the patent is ever invalidated, you can stop paying.

They can just pay out any income as soon as it shows up so there is nothing to recover if their patent is invalidated.

PS: The only way to make this work is if you pierced the corporate veil when their patents where invalidated, and that would make patents even more useless to small companies.

Personally I think we should just abolish the entire patent system, since I really don't see much benefit in it for anyone but large companies, but basically everyone agrees on stopping patent trolls with garbage patents