Postfix SMTP "The IP you 're using to send mail is not authorized to 550-5.7.1 ..." to Gmail

We just rolled out a migration of a VM pro server. The only significant differnce is that we upgraded the OS from Deb 5 to Deb 6 in the process.
Everything looks to be working fine with one frequent exception in the mail logs

Nov 4 18:04:55 lamphost1 postfix/smtp[28694]: 143C27292F: to=xxxxxxxx@gmail.com, orig_to=xxxxx@xxxxx.COM, relay=gmail-smtp-in.l.google.com[74.125.65.27]:25, delay=1, delays=0.33/0/0.19/0.49, dsn=5.7.1, status=bounced (host gmail-smtp-in.l.google.com[74.125.65.27] said: 550-5.7.1 [xx.xx.xx.xx] The IP you’re using to send mail is not authorized to 550-5.7.1 send email directly to our servers. Please use the SMTP relay at your 550-5.7.1 service provider instead. Learn more at 550 5.7.1 http://mail.google.com/support/bin/answer.py?answer=10336 r8si1735123ybf.44 (in reply to end of DATA command))

The virtualmin install was with the install.sh script and Postfix was configured exactly as was the server this box took over for - with the exception of hostname, ip, etc. But on the old server we never had this problem with Gmail outright rejecting everything from us.

I’ve check to see if the server is blacklisted for any reason and it is not.

Chris

Howdy,

Is your server by chance setup on a residential connection? The error you’re getting sounds as if the IP address is flagged in some way, perhaps as being a dynamic or residential line.

-Eric

No, it’s neither residential nor dynamic.

I’ve searched Google for more information and came up with this:

In order to prevent spam, Gmail refuses mail when the sending IP address does not match the sending domain. To send mail from your server to Gmail, we suggest using the SMTP relay provided by your ISP. Please note that we are unable to whitelist IP addresses or otherwise make exceptions at this time.

So how is it that my other server, with the same settings, could send to gmail just fine, but this new server cannot when all that is different is basically the IP address of the our box? And just what am I supposed to do with mail generated ON the server through PHP scripts and such? This makes no sense - or am I missing something in Postfix?