[kobalsky]

I wonder if adding a random salt for each account would help in that situation?.

bcrypt(md5(password) + salt) + salt

the problem with password shucking would be that they just do a bcrypt(md5) over the list of md5 hashes they have and check if they exist in your database.

but if each hash is salted they would need to run every their complete md5 hash list through bcrypt for each account instead of once per database.

[Aissen]

No that wouldn't help because you'd need to store the random salt along the hashes. So you can still do: bcrypt(other_leaked_md5 + salt) to shuck it (i.e confirm if both are the same, and skip the bcrypt on your stronger service). The defense is a global "pepper" that would be in the code but not the DB, assuming only the second one leaks.