I've figured out what's going on. The messages are coming to the server from remote hosts via UDP. I didn't notice the host field changing at first, my mistake.
BTW, actually there is a possibility to login using public key authentication with no
authorized_keys file involved. RedHat (and variants) have a supported patch for OpenSSH that adds the
AuthorizedKeysCommandRunAs options. The patch has been merged upstream in OpenSSH 6.2. To quote from the man page:
Specifies a program to be used for lookup of the user's public keys.
The program will be invoked with its first argument the name of the
user being authorized, and should produce on standard output
AuthorizedKeys lines (see AUTHORIZED_KEYS in sshd(8)). By default (or
when set to the empty string) there is no AuthorizedKeysCommand run.
If the AuthorizedKeysCommand does not successfully authorize the user,
authorization falls through to the AuthorizedKeysFile. Note that this
option has an effect only with PubkeyAuthentication turned on.
Specifies the user under whose account the AuthorizedKeysCommand is
run. Empty string (the default value) means the user being authorized