One of those uses multiple domains (it's an iCloud account that I registered way back in the iTools days, so it supports @mac.com, @me.com, and @icloud.com....possibly even @itools.com, not sure about that one).
I regularly use a + extension to the addresses that support it when I'm signing up somewhere that I don't 100% trust, and that allows arbitrary additions to the address. And I don't always remember what version of a site's name I will have used (eg, user+hn@example.com, user+hackernews@example.com, user+ycombinator@example.com, etc).
I recognize that I'm an outlier, but trial and error is completely infeasible in this scenario.
ie <email prefix>+<tag>@gmail.com
That tag could be anything or everything.
I do wonder though -- if the hash secret gets out then I think we're right back to where we started... it would be easy to cross-reference leaded email DBs with the dumped DB and work backwards. I'm now a bit less sure this does much for use privacy against an even slightly motivated opponent (one who would almost certainly have access to at least one dump of previously-exposed emails)...