It's possible to update everyone's password without them logging in. If the old storage was just MD5(password) and you want to update it to MD5(bcrypt(password)), you're out of luck. You need the plaintext password to make that change. If instead you change your new storage to MD5(bcrypt(MD5(password))), you can take all of the hashes currently in your database and update them at one time with MD5(bcrypt(old hash value)).

Great point. Never occurred to me to do it that way.

The proper solution would have been to flag the old passwords and require everyone to change them on the next login. After a couple of months you null out the remaining passwords and require anybody coming back to go through the password reset system.

As far as I know, that is correct.[1] Any change, whether for work factor or algorithm in code still waits for the user to come back and attempt a login, at which point you update the database stored attributes and the hash.

I think that if you can update a user's password without them inputting, then you have two problems.

[1]not authoritative advice.

edit: seems that comments suggest doing the md5(bcrypt(hash)) can be used to upgrade across the board

I thought that a while ago but then someone just pointed out that you bcrypt hash the MD5 hash and support two step (MD5 then bcrypt) until they login at which point you can rehash using only bcrypt.

That's a much smarter approach. Never thought of that.

Depends, if your old hash is H1, then you can migrate to a scheme H2(H1(password)), with a second hash H2, provided H1 is not too broken.