use something like the hash of UID + a salt to determine the point?
That's what I did. It just takes the first byte of the SHA-1 hash of UID+salt and adds it to 775. There aren't many users with more than 775 activity, so checking people for upgrades every 10 minutes doesn't cause any problems. I was able to do it with just one SQL statement because MySQL has a built-in SHA-1 function.