The current implementation of the NFS UID and GID lookup works by running 'getent passwd' with an assumption that it will return the entire list of users available on the OS, local and remote (AD/etc.).
This behaviour of the command is advised to be and is prevented by administrators in most secure setups to avoid excessive load to the ADs involved, as the # of users to be listed may be too large, and the repeated requests of ALL users not present in the cache would be too much for the AD infrastructure to bear.
The NFS server should likely do lookups based on a specific UID request, via 'getent passwd <UID>', if the UID does not match a cached value. This reduces load on the LDAP backed infrastructure.
Thanks qwertymaniac for reporting the issue.