It's not really a primitive, but I'll concede the point. Similarly the one about 50 iterations, that was somewhat silly (there is a reason I have that number in mind, but I won't bore with details).
However. Mythical situation? Try a good portion of shared PHP hosting; why do you think the most popular software in the world (i.e. stuff like Wordpress) still supports MD5/Sha hashing?
I realise this is not a problem you may have come across before; but don't imagine it does not exist :)
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.
However. Mythical situation? Try a good portion of shared PHP hosting; why do you think the most popular software in the world (i.e. stuff like Wordpress) still supports MD5/Sha hashing?
I realise this is not a problem you may have come across before; but don't imagine it does not exist :)