ssh login attempts fail randomly - but work otherwise for same user

I'm having strange ssh login issues, where the login for a user does work in general, but sometimes it doesn't. here's a failed login attempt:

Mar 28 14:49:55 hostname sshd[32247]: Invalid user sshuser from 172.16.1.19
Mar 28 14:49:55 hostname sshd[32247]: input_userauth_request: invalid user sshuser [preauth]
Mar 28 14:56:02 hostname sshd[29513]: pam_unix(sshd:session): session closed for user sshuser

which is strange, because the previous login attempts worked just fine:

Mar 28 14:49:04 hostname sshd[32117]: Accepted publickey for sshuser from 172.16.1.19 port 56766 ssh2
Mar 28 14:49:04 hostname sshd[32117]: pam_unix(sshd:session): session opened for user sshuser by (uid=0)
Mar 28 14:49:04 hostname sshd[32117]: pam_unix(sshd:session): session closed for user sshuser

As you can see, the previous login attempt by sshuser was successful just a few seconds before.

What could be causing these problems? sshuser is a network user that's pulled in via NIS. I do not see any timeout problems on either the client or the server.