I'm not sure whether POSIX warrants anything about this behavior, but nothing prevents a process from running with a UID not listed in /etc/passwd (or NIS, whatever). For example, sudo allows running a command with a UID not listed in the password database, see http://linux.die.net/man/5/sudoers :
"""
targetpw

If set, sudo will prompt for the password of the user specified by the -u flag (defaults to root) instead of the password of the invoking user. Note that this precludes the use of a uid not listed in the passwd database as an argument to the -u flag. This flag is off by default.
"""

UIDs not backed by users are useful for example if you're working with a sandbox, or virtual users such as in some FTP servers http://www.proftpd.org/docs/howto/VirtualUsers.html :
"""
Question: What makes a user "virtual", then?
Answer: A virtual user is, quite simply, a user that is not defined in the system /etc/passwd file. This file associates a user name, given by the system administrator, to a user ID (commonly shortened to UID) and a group ID (GID), among other details. The Unix kernel does not deal with users in terms of their user names; it only "knows" about UIDs and GIDs. This means that an application like proftpd can look up the IDs to use for a given user name however it sees fit. Using /etc/passwd is not strictly required.
"""