If they could just fix it, it seems like they must be storing user credentials insecurely. At least, I can't figure out how to fix something like this without at least a password change for all users.

You mark the existing hashes as “only use the first 8 characters to compute the hash” and, from now on, clear that bit for every password that gets changed and for new accounts.

When all bits have been cleared, remove the logic for inspecting the bit and the mark bit. If that takes too long, force your users to update their password at whatever pace suits you.

Oh I wouldn't be surprised.

A few years later I actually had visibility inside that bank due to my work. There was a whole IT team dedicated to "review this and fix the horrible decisions we made in the past". I didn't have visibility to their web interactions / front end and such but it wouldn't surprise me if that was just as much a project to clean up.

To their credit whenever I talked to the "clean up" type team they were super sharp guys and quite willing to listen to outside vendors (me) who sometimes saw stuff the guys inside maybe didn't.

easy enough; on next successful login re-hash the full length of the password and store it.

That would be somewhat risky; the user might have mistyped the password somewhere in the part that up to now got ignored.