What about performing the hashing again, on the existing hash (of course it would be simplest to encrypt from the beginning when user logs in again, but just for discussion's sake). Let's say we have a legacy db with hashes created with small work factor. We could simply perform the hashing on these previous hashes (increasing work factors as appropriate). We could simply annotate the fact that one have to perform the hashing two times.

Of course we're 'overthinking' it again, but is the above solution viable?