The salts should be different for each user, specifically to deter brute forcing of this nature.
The only time you would have access is when the user logs in, so for rarely logged in users you would have to proactively reset their password or cross your fingers.
Hopefully you don't transmit the password and are doing challenge/response so that you don't even have it when the user logs in.
But even with 12 round bcrypt hashing, you should be able to fairly cheaply attack a list of 2,000 bcrypted passwords with a million-entry database of leaked e-mail/password combos in a GPU-month.
Probably easier to force a password reset on everyone and then do the checking on password change, although you need to be careful there not to be sending the password.
EDIT: uhm, wait, so if you've got the e-mail address in the dump then there's only one user for that, so just grab their salt and hash the password and check it. So that million entry database should be checkable in a bit over half an hour...