Your assertion about the salt is wrong. That's not what a salt is designed to prevent. A salt is to prevent pregenerated tables from being meaningful, therefore 32-64bit is plenty.
'good probability' is a little dramatic too. The birthday paradox would only apply if every user had the same password to begin with. With 32 bits, you would need about 77000 users with the exact same password to get to 50% probability of two having the same salt/hash. 2000 users with the same password is 0.1% probability of two being the same.
If you are concerned about equalities because you have thousands of users with the same password, input the username into the hash generation function as well. Don't waste space with needlessly large salts.
Let's consider Adobe, since we have actual data. Of 130,324,429 users, we know 1,911,938 chose the password '123456'. Consider just that population of users.
Assume a 64-bit salt was chosen uniformly at random for each user. The probability that this cryptosystem is catastrophically broken (i.e. leaks password equality between users in just this population) is about 2^-23. That's not good -- usually cryptosystems are designed to have a probability of failure between 2^-80 and 2^-256. Now multiply that up for each population of users choosing the same password, and you're in trouble.
Adding in other user-unique data is definitely a good idea!
> is about 2^-23. That's not good -- usually cryptosystems are designed to have a probability of failure between 2^-80 and 2^-256.
The failure cases are different though. Cryptosystems that require a strength of 80 to 256 bits are measuring their strength against an adversary brute-forcing or performing some other active discovery.
In this case, it's just the probability that two users will pick the same password and get the same salt. The attacker doesn't get to run many guesses, the database is just leaked 'as-is' and the hashes either show equality or they don't. So there is only a 1 in ~8mil chance that two in that group will show equality. Not bad for such a large population.
It doesn't then multiply up for each population. It's a sum since they are independent groups. Even then, the probability for each subsequent group will be vastly smaller as the population size decreases.
Finally, the only population at risk is users that chose such blindingly obvious passwords that they ended up in a large password population pool. These would be the same accounts that would be revealed almost immediately anyway since the obvious passwords is where any brute-forcing tool worth its salt (pun intended) would guess first.
'good probability' is a little dramatic too. The birthday paradox would only apply if every user had the same password to begin with. With 32 bits, you would need about 77000 users with the exact same password to get to 50% probability of two having the same salt/hash. 2000 users with the same password is 0.1% probability of two being the same.
If you are concerned about equalities because you have thousands of users with the same password, input the username into the hash generation function as well. Don't waste space with needlessly large salts.