I use Postini for all domains on my server.
dig sees the following for my domain (replace domain.tld with your domain):
; <<>> DiG 9.2.1 <<>> domain.tld mx
;; global options: printcmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 12969
;; flags: qr rd ra; QUERY: 1, ANSWER: 4, AUTHORITY: 0, ADDITIONAL: 0
;; QUESTION SECTION:
;domain.tld. IN MX
;; ANSWER SECTION:
domain.tld. 86400 IN MX 200 domain.tld.s6a2.psmtp.com.
domain.tld. 86400 IN MX 300 domain.tld.s6b1.psmtp.com.
domain.tld. 86400 IN MX 400 domain.tld.s6b2.psmtp.com.
domain.tld. 86400 IN MX 100 domain.tld.s6a1.psmtp.com.
And, of course, this is for Service Center 6 with Postini--your records may be different.
How do you have Delivery Manager set in Postini? I use IP address instead of a DNS record.
You should also be able to get a response from Postini's servers by either telnet'ing to the record with the 100 precedence (my s6a1.psmtp.com record). Or you can check from
www.dnsstuff.com and run their DNS Report (upper left hand corner). It will actually report, in yellow, a warning that the domain name doesn't match with a reponse from psmtp.com in the string.
Also, make sure that any MX records that are direct to your server (no psmtp.com section) are set to a higher precedence number, such as 500, in the case of the above records.
If I can be of further assistance, please let me know.