I believe you’ve made a cardinal mistake, and in fact, your md5(‘deliciously-salty-’ + password) (md5 can be replaced with SHA-2 or any other hashing algorithm) is vulnerable to the very same rainbow table attack!
With a fixed salt (the ‘deliciously-salty-’) part, one can compute a rainbow table for that algorithm and that salt, and crack any arbitrary password (with the larger the table, the more classes of passwords that you can crack).
The correct way to store passwords is to store two values for each user: a salt (which is a randomly generated string of any length, the longer the better to a point), and hash(salt + password). That way, you cannot compute a rainbow table, and cannot crack the password.
As for the speed of a hashing algorithm being a vulnerability, you may be wrong. The security of the algorithm is the important part. md5 is a technically broken algorithm, and SHA-2 is technically better, but we are talking about security experts here - their idea of broken is different than ours. For all practical purposes, especially in this use case with the combination of random salt, md5 is still secure. See http://en.wikipedia.org/wiki/Md5#Vulnerability
For example, for www.goruneasy.com, I used this md5(random-salt + password) method. The salt is a 10 character string, using characters where each character’s ASCII value is between 1 and 253, creating an incredibly large potential space. I don’t believe, unless a truly massive vulnerability is found in the md5 algorithm, that this approach can be compromised.