>which implies already having high privileges. (How do users with such high UIDs come into existence?)
I am not so sure about that. I work at a smallish, place and by default my AD account has UID of 945004649. Still under the INT_MAX but not that far off. Our domain controller is running Windows 2012 R2, and nothing was changed or touched regarding UID's, everything was left at the default. We just create users and get whatever UID AD assigns.
This could happen anywhere. If you know that dynamically created users are in range {x} and AD/LDAP users are in range {y}, then a good sysadmin would choose a very high range for batch creations of specific types of accounts. This is fairly common practice. Modern Linux and Windows can support millions of UID's, so it is perfectly reasonable to say, "We are going to use range {y} for this project then nuke that entire range when we are done".