Sounds like the problem would be in other parts of the logic. Is total calculated once for the whole file, and you run it again and again for each user, or how do you end up with that total?
A common technique is to keep an array of totals where the keys are the users, so you only have to run over the file once.
Code:
awk -F : '{ if (++total[$1] > 500) print $1, $2 }' file
(This will print multiple times, once for each record after the total is exceeded. Figuring out how to avoid that is left as an exercise.)
Once you get it to print what you want, just pipe that output to
sort.
