Send me the scripts for the Queue, Service, Event Notification, and Activation Procedure by email through my blog. Let me know what specific version of SQL Server you are running, and the Edition, or just copy/paste the output of SELECT @@VERSION into the message so that I can match your environment and I'll see if I can repro this and offer a complete fix.

Did you dump all of the messages from the queue and look at them to see if there is a problem with one?