Hmm, my perl script needs only a week to brute force a password with a length of 6 characters with a base of 62 characters and there are online databases. So I recommend forcing long passwords =)
There are precomputed hashes available for every password up to length 9 or 10 using every typable character on a keyboard (around 100 characters), and longer passwords can often be bruteforced more efficiently using a dictionary based attack, since many people often use a combination of words for passwords.
ie: I use a password of "turkeygobble", which, with a small alphabet of 26 characters and a length of 12 has 95,428,956,661,682,176 possible permutations. However, if I have a small dictionary of 1,000,000 words, and both of the words used in my password are in my dictionary, it's guaranteed I'll brute force the password in only 1,000,001,000,000 iterations. Which is only about 0.001% of the work of bruteforcing the password on a character by character basis, IF we knew it was 12 characters long beforehand. If we didn't, there would be about 4,000,000,000,000,000 more possible passwords to try, which is still more than the possible number of passwords with our dictionary.
The best bet is to force people to use symbols (!@# etc) to simultaneously reduce the number of dictionary matches (and dictionaries nowadays contain words that have been turned into 1337-speak, so try not to use those and think you are safe)and increase the complexity, and to also enforce a minimum of ie: 12 characters.
Note that even with a small alphabet of only 26 characters, as long as the password is long and doesn't contain dictionary words or patterns(is random), it's still very secure.
A salt is a very good idea as well, so long as it's well chosen. A very good salt can be generated by pre-computing the md5 of a simple word. Then, combining that md5 with the password the user entered, and md5'ing the entire thing will result in a very secure md5 that will not be bruteforced, so long as the salt you used remains a secret. In the case where you can't expect the salt to remain secret, md5'ing the password twice and saving that is recommended, as it increases the amount of work that needs to be done per password.
