If I had to guess, I would vote nscd.
One thing I would try:
watch --interval=.1 "getent passwd | grep username"
This will allow you to see in tenth of a second intervals what PAM sees via NIS.
If you are having some sort of a caching issue, this may point it out to you. If it goes blank - you've lost the entry in the cache. See how long it remains missing.
If it is indefinite, I would bounce nscd, and see if it comes back.
It could be the lag for your LDAP query. What is your pam_login_attribute set to?