> would this have any use or decrease the security of those user accounts at all
Yes:
http://www.pxdojo.net/2015/08/what-i-learned-from-cracking-4...
Now, this assumes typical storage, that "leaking the password column" means leaking hashed password+salt. Without the salt, things would go slower - but it's sort of an artificial constraint - what you're talking about, is leaking the stuff the server needs to have to check a valid password. And that generally means the hash and the salt.
More generally, there's an upper bound on how difficult it can be made for the server to verify a password; conceptually this is: ((the amount of time a user is willing to wait to be logged in) - overhead) / (resources available on the server for checking the password)
Ok. You don't actually divide the time by the resources, but the point is that if you have 10.000 (valid) logins a minute, you probably can't dedicate 4 high-end GPUs on max throttle for 1 second to check every login attempt.
But an attacker might have those kind of resources. Which means, there's a very real practical limit to how hard it can be made to validate a password guess (a cracking attempt) -- and it will be some small fraction of the time your server takes to validate a login.
Which means that no "easy" passwords (eg: dictionary words) are ever "safe" passwords (safe against an off-line attack).
My guesstimate (mostly pulled out of thin air, and late night napkin "calculations") are that for any password to be "secure" it would need ~64 bits of entropy. Maybe that's a high estimate, given a solid work factor, but I don't think so.
The problem is, that 64 bits is actually quite a lot of information to memorize. In short: you'll likely only remember one or two such passwords. Use them to lock your password manager, and have machine generated random passwords for the rest (because what you don't want is to ever re-use passwords, as passwords are generally always susceptible to sniffing, shoulder-surfing, being filmed, keylogged or otherwise captured in plain text).
For a little more about some of my thoughts on generating passwords that are secure, friendly to current systems ("password rules"), friendly to humans (feasible to remember and type from memory without visual feedback), see these comments: https://news.ycombinator.com/item?id=11772700
(I keep coming back to this idea, but so far I've concluded that 64, 96 and 128 bits is rather a lot to type in, almost no matter how it's encoded. So I'm not sure how useful such a system will end up being. But maybe I'll finally just prototype it, and ask for help in testing it (the "security" part is intentionally trivial, but the usability part is the interesting bit -- will it actually help us in using secure, machine generated passwords, or will we still have trouble remembering them?)