Could you not use an adaptive password hashing algo with an absurd iteration count. Let's say each hash takes 500ms. Salt each domain with a different salt.

Building a rainbow table would still be possible, but hindered. To discover one domain behind one hash, you would need to roughly run through half of the used domains with the slow password hash.

That being said, the subset of popular domains is much smaller then the full set of domains, so the problem can be pared down to be much more effective than the worst-case.