We have a couple of domains that our users email regularly that have started to not deliver mail sent from us to their mailboxes.

This started around 2 weeks ago with users reporting the following message :

This is the mail system at host MY.DOMAIN

I'm sorry to have to inform you that your message could not
be delivered to one or more recipients. It's attached below.

For further assistance, please send mail to postmaster.

If you do so, please include this problem report. You can
delete your own text from the attached returned message.

The mail system

<USER@THEIR.DOMAIN>: host xxx.xxx.psmtp.com[xx.xx.xx.xx] said:
550 mailbox unavailable - psmtp (in reply to RCPT TO command)
We don't run Postini (psmtp) and the email address on their system was definitely correct.

I emailed their postmaster who whitelisted our address.

Today, two weeks later, I find that another separate domain is putting mail from our domain in quarantine. We're getting no 550 bounce but their users are getting mail :

These messages were quarantined before they reached your inbox as potential spam and virus-infected messages. The quarantined messages can be delivered by clicking on "deliver".
The deliver link goes to

After this it turns out that users on the original server that was sending the 550 mails haven't been receiving mail, some for up to two weeks.

I've used mxtoolbox / barracuda etc and we're not an open relay and not on any RBLs. There's nothing in my logs.

It seems Postini has it in for us. Any ideas what to do about this ? We don't use Postini and so have no access to their support.