BTW -- this question/answer updated for today's OS's.
Quoting from redhat: managing unique UID and GID Number assignments, it describes usage of UID and GID's and their management and how generators (ID servers)
must generate random UID and GID values and simultaneously ensure that
replicas never generate the same UID or GID value. The need for unique
UID and GID numbers might even cross IdM domains, if a single
organization has multiple disparate domains.
Similarly, utilities that allow access to the system may behave unpredictably (same reference):
If two entries are assigned the same ID number, only the first entry
is returned in a search for that number.
The problem comes when the concept of "first" is ill defined. Depending on the service installed, usernames may be kept in a variable sized hash that would return a different username based on inconsistent factors. (I know this is true, as I've sometimes tried to use 2 usernames w/one ID, one being a local username, and the other being a domain.username that I wanted to map to the UID (which I eventually addressed in a complete different way), but I could log in with "usera", do a "who" or "id" and see "userb" OR "usera" -- randomly.
There is an interface for retrieving multiple values of UID's from a group (groups with a single GID are designed to be associated with multiple UID's), but there is no portable interface to return a list of names for one UID, so anyone expecting the same or similar behavior between systems or even applications on the same system may be unhappily surprised.
In the Sun (now oracle) yp(yellowpages) or NIS(NetworkInformationServices), there are also many references to requirements of uniqueness. Special functions and servers are setup
to allocate unique ID's across multiple servers and domains (example is the uid_allocd, gid_allocd - UID and GID allocator daemons manpage
A third source one might check is Microsoft's server documentation for NFS Account Mapping. NFS is a unix file share protocol and they describe how file permissions and access is maintained by the ID. There, they write:
UID. This is an unsigned integer used by UNIX operating systems to
identify users and must be unique in the passwd file.
GID. This is an unsigned integer used by the UNIX kernel to identify
groups and must be unique in the group file. MS-NFS-management
While some OS's may have allowed multiple names/UID (BSD derivatives, perhaps?) most OS's depend on this being unique and may behave unpredictably when they are not.
Note -- I am adding this page, as someone referred to this dated entry as support for modern utils to accomodate non-unique UID/GID's... which most, do not.