I would say that, given how 'cheap', you could slowly increment the cost-factor over time. You could also ask a user to replace their password after a certain t

I would say that, given how 'cheap', you could slowly increment the cost-factor over time. You could also ask a user to replace their password after a certain time period, or after the cost factor gets too 'low' - you can even allow the same password to be entered. Having a different cost-factor for every password is a bit of a logistical nightmare though. The fact is that any significantly high cost factor is much better than md5, sha1 or any other normal hashing function, and should prevent password cracking for 5-10 years. This is a reasonable period of time.