Authentication tried for root with correct key but not from a permitted host

Syslog tells me, for every key-based SSH login attempt (OpenSSH_5.5p1 Debian-6):

Authentication tried for root with correct key but not from a permitted host (host=foo.ex.com, ip=10.0.0.3).
Authentication tried for root with correct key but not from a permitted host (host=foo.ex.com, ip=10.0.0.3).
Accepted publickey for root from 10.0.0.3 port 53187 ssh2
pam_unix(sshd:session): session opened for user root by (uid=0)
Received disconnect from 10.0.0.3: 11: disconnected by user
pam_unix(sshd:session): session closed for user root
Yet the login succeeds, despite these warnings. This has been posted on debian-security a while ago, but nobody replied. (or will be able to reply now). So, I wonder what's going on here...