This is an SMTP question rather than a Perl one. The first step would be to try just changing the "-f" address (the envelope sender) to something gmail, to see if that works. If not, you'll want to find out why your message is being rejected, either by looking at the logs, or by talking a bit of SMTP by hand. Basic SMTP is actually pretty easy -- look at RFC 822 for details, then telnet from your server to port 25 on the recipient's mail server and play around.
Just another Perler interested in Algol Programming.