Load breach data before verification/email
Not sure if this is done already.
I suggest the breach data is loaded on the DB as quickly as possible, independent of verification. The idea being some of your services such as checking if a password is part of a breach only need to know if a password is part of a breach. The email notification and other parts of the service would wait for verification.
If your data structure requires a record for the breach source; if so could it have a record with a status of unverified?
For those users protected by a password manager/site that checked against your bad passwords, they would be informed earlier. This could help your verification process, as a small portion of the users may contact the support for that site saying their password was compromised, adding legitimacy to your attempts to contact the company.
If you have breach data then the users in the breach are at risk regardless of verification.
Passwords are typically only updated when a large corpus of plain text versions appear. Most breaches have the passwords already hashed which means there's nothing we can do with them in HIBP, including loading them before verification. Where we do have passwords in plain text, they're already processed independently of the email address loading process.
tl;dr - it already works this way 🙂