Domain Emails boucing from Postini (non-domain emails are fine)

[#1]

One of my referrals is having problems.
They just had their domain transferred in to their broadband account yesterday.  The domain went live on the account yesterday and yesterday evening the website was working correctly. However there was still no sign of any emails. It was sucking in emails.... but not delivering them or bouncing them.
However, I have in the last hour started receiving bounce messages for test emails I sent to them today and yesterday. Each of these messages is getting further back in time, so appears that the whole stored mail queue is now being delivered to Postini, which is then rejecting the email with a permanent bounce message. I am concerned that every minute that goes by, more of the up-until-now stored email is being dequeued to Postini, bounced, and permanently lost!
Can we put a urgent halt on this dequeuing, or get Postini to accept and deliver the mail correctly.
It is not my account, but a ticket has been raised on the account under ID: 23972536 (which should reveal the account and domain name concerned)

Bounce messages look like this:

This message was created automatically by mail delivery software.
A message that you sent could not be delivered to one or more of its
recipients. This is a permanent error. The following address(es) failed:
<mailbox>@<domain>.co.uk
SMTP error from remote mailer after RCPT 
TO:<<mailbox>@<domain>.co.uk>:
host <domain>.co.uk.s5a1.psmtp.com [64.18.4.10]:
554 No relaying allowed - psmtp

I phoned support, but was told the "only postini guru" is in a meeting. I asked if there was someone else who knew about these things, but was told it was best to put it in a ticket (which I have done for the referral).
Was hoping someone here might be able to advise... or another internal "postini guru" might be able to intervene before the whole mail queue is lost.... (it might of course already be too late for that!!!)
Mike

[#2]

We're getting this looked at asap, Bob is getting the domain added and is checking to see if there is a broken process. Sorry about the hassle.

[#3]

Thanks guys.
It is so frustrating to be sitting here powerless, knowing that every second, is another few email probably lost.
I'm suspecting that by now most will have gone through postini and therefore bounced.
I just got a phone call from the original support guy saying it had been escalated to networks team (which was interesting he phoned me not the referral, since he didn't have my number - unless he got my details from this posting).
<added> Just found out from the referral that they gave the support guy my mobile number... so that mystery is solved! They didn't have a clue what he was trying to tell them, so told him to phone me!!! </added>

[#4]

Yep, should be added shortly. The emails sent to the domain so far though are likely to have been bounced as a 554 is a permanent rejection.
Please apologise to your referral for the hassle. I've raised problem 49550 to investigate why the process to add the domain to the Postini engine broke.

[#5]

New test email I just sent to the domain is arriving correctly.
Thanks Bob (and everyone else).
However, do you know if the full queue had de-queued, and therefore all old emails lost? Or were there any old ones left?
Obviously the referral will know this when they do or don't arrive in due course! (but I won't unless I ask them).
Mike

[#6]

Mike,
Sorry to say it but I'm pretty sure the majority will have been returned to the sender (although it does depend to some degree on the sending server. Email from some sources may not generate a bounce at all)

[#7]

Bob,
Thanks for the reply. I feared that would be the case.

For your reference:-
I did find it hard to "hear" the sincerity in your apology with that monstrous jiggling avatar gyrating away though!!! 
I actually don't dislike it per se... as it is fun. However, it is amazing how it undermined the message you typed to me. I was very surprised, but I found the avatar genuinely off-putting when on the receiving end, in this sort of scenario.
Seriously, speaking it might be worth changing the avatar, as it would be a shame to upset an annoyed customer further by your avatar undermining you words!
I fully appreciate your apology, and I'm sure others who know you here (and know the good work you do) would be able to see past the avatar too... but equally it might not help others!
I hope that helps you...
Thanks again for the support
Mike

[#8]

Looks like that makes two of you now
It won't be around for too long, don't worry.