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.)