I am getting the same message as well. We are up to date as of 20 minutes ago. I have attempted to force the messages to be sent, I have restarted psa and qmail multiple times. I have no DNS errors and everything in the queue is an authorized host.
Currently have about 70 in the queue and that is very high - usually we only have 2-5 at any given time.
One difference is that we are running inside of openVZ and we have disabled IPv6 for the host machine to avoid these headaches, so I am unable to set a fake IPv6 address. This does appear to be a fairly new issue but we are uncertain when it started. We have not changed anything on the system other than keeping packages up to date.
Running a custom 2.6.32 kernel with Ubuntu 10.