So use PHP-ass: http://www.openwall.com/phpass/. It's integrated into Wordpress and does all of that stuff, including falling back to md5 if you have a really crappy host.
But really - it's just another reason not to use PHP, and not to have a crappy webhost. You could probably say much the same things about backups, app security, bad UI or design. But for most people, don't do that is apparently not a good enough answer.
Update: Just looking into how Django stores passwords, and it does much the same thing (although it falls back to SHA-1, rather than MD5). There was a push to use bcrypt a while back, but it got marked wontfix, due to "backwards compatibility issues". Sigh.
But really - it's just another reason not to use PHP, and not to have a crappy webhost. You could probably say much the same things about backups, app security, bad UI or design. But for most people, don't do that is apparently not a good enough answer.
Update: Just looking into how Django stores passwords, and it does much the same thing (although it falls back to SHA-1, rather than MD5). There was a push to use bcrypt a while back, but it got marked wontfix, due to "backwards compatibility issues". Sigh.