In my hypothetical offline-validator scenario, it doesn't have to scale because it's not running at transaction time. Go ahead and reset the password, generate a bunch of new fake hashes and store the index of the "real" one in the same log that will be picked up for validation later on. With asymmetric encryption, the log could be stolen outright and be of no use at all to an attacker.
That said, I'd probably lean towards an online validator just so I could stick attackers in a honeypot and keep them from messing with my users. Though, as someone else pointed out here, by far the most likely use for the stolen passwords is not on my site, but to use them to log into bank accounts.