If hibp started using something that guarantees k-anonymity when checking for an email, like their password service does[1], then I think it'd be possible to keep the email unique.

1: https://www.troyhunt.com/ive-just-launched-pwned-passwords-v...