NO! This is a bad idea:
"When a user logs in, you retrieve the salt for the given user, re-compute the hash as you normally would, and simply check if the resulting value EXISTS in the Hashes table. If it does, you consider the login as successful."
This will cause false positives. Let's say that of the trillions of hashes, one is the one we want... But what if one brute forces the system? What if one of the brute attempts matches ANY of those trillions? Bam. Access.
This is a very very bad idea.
Do not roll your own security unless you know what the F&#@ you're doing. You are trading a compromised security issue (your attacker already has access enough to get the hashes/users) for a uncompromised security issue (your attacker does not have access to the hashes/users, and is just trying to get in via brute force).
You are making it easier for the non-secure access attacker by making it harder on the secure access hacker. You are making the most common threat bigger to make the least common threat smaller.
Let me explain it using the pigeonhole principle.
Say you have 2 pigeons (passwords) and 1 million pigeon-holes (hashes aka possible passwords). Assuming all the pigeons are in a hole, and you reach into a random hole, what is the chances of pulling out a pigeon (password/hash collision)?
Now, let's say you have one hundred thousand pigeons (What OP is suggesting) and the same million holes... What are your chances of pulling a pigeon out of a random hole this time?
I wish I could use font-size 1000px right now.
Do not do this. Do not do this. This is a compromised system, right off the bat. If you are securing people's private data or possessions in this manner, you are doing them harm.
As more users sign up, the chances of brute forcing actually increases (more hashes to possibly match!). Let me repeat that in a different way: EACH USER MAKES THE SYSTEM LESS SECURE.
Besides all that, let's say you have to do an EXISTS check on a million records. That means you will check each one until you find a match. That is a linear complexity, that is O(n), unless you index the column, which is expensive. Could take a while, depending, but most certainly will take longer than searching for something with a known key that is indexed efficiently (being an index on a primary key), which should give you something like O(log n) which is much faster.
I don't mean to be an ass, but please downvote this so that there is less chance of people implementing this.
OP; you are suggesting a very harmful idea. Remove it if you have any amount of goodwill towards the community.
I work in web security, and used to work for a credit card merchant processor. At one point, I had access to and had to secure millions of accounts with authorization information for their credit cards; this being information one could use to empty a bank, no questions asked.
I Really Know what I'm talking about. THIS IS A BAD IDEA.