MD5 is better than plaintext, but only marginally.
If you use bcrypt with a salt, to find all records with email
email@example.com you would need to hash that email one time per record with that records unique salt. That would quickly get out of hand, and as you note in your question, not work.
What you can do instead is to use a constant salt that is the same for all records. Then it is no longer called a salt, but a pepper. The value of the pepper should be random and treated with the same care as a cryptographic keywith the same care as a cryptographic key, since without it a brute force on the hashes is practically impossible.
It is important to understand that a pepper is not as secure as a salt, since a brute forcer in possession of it would get the same speed up from not having to compute the hash one time per record as you do when searching. But it is a lot better than using a fast algorithm like MD5 or SHA-256.
A practical note: Not sure if all bcrypt implementations allow you to specify the salt yourself, and all of them will have the salt included in the output. You need to cut that part off before you store it, since the pepper should not be stored in the database.