We have had a similar issue with our Brightmail Gateway, however we were unable to release ANY messages from quarantine.
Anytime we tried to release a message from the spam filter (keep in mind this was ALL messages) we would get the error:
'Cannot release the message. It has either been released or was unable to contact the SMTP host' This error would display, in red, on the actual Spam filter tab.
The brightmail log error however was:
Jun 07 2010 13:45:36 [http-41443-Processor8] ERROR - com.brightmail.common.BrightmailException: null ; nested exception is:
com.sun.mail.smtp.SMTPSendFailedException: 501 bogus mail from
Are you seeing this error in your brightmail log at all?
We have two mail servers (Exchange and IPSwitch iMail), we were able to resolve this for the iMail server and are working on a solution for our Exchange server. If you are seeing this same error, i'd be happy to share the fixes on our end. Otherwise, it is probably a different issue.