"given that the salt is a constant per user"

Just use a different salt for each password, not each user

Edit: You're probably right about everything else.