Currently we have a POP3/SMTP email server (IMAIL).  Our end users connect to it using Outlook.  If we are on out local intranet or the end user's local ISP's are not blocking port 25, we are able to send emails without a problem.  If they are blocking port 25, then we can't send emails.

I'm looking for solutions to overcome this obstacle.  Here are details about the network infrastructure and things we've tried:

We have business level cable internet provided by Cox Communications.  We have a public IP tied to our public DNS record.  This points to our Linksys RV042 router.  The router directs all HTTP and SMTP traffic to our DNS server which is also our DHCP and email server.  We currently only use port 25 for SMTP and have rules setup to only allow outgoing SMTP traffic from our email server's IP address.  We have PPTP server enabled on our router.  We use Windows built in connection wizard to create a vpn connection to the PPTP server of the router and can successfully make a connection.  This connection will allow access to network drives etc, but it will not allow us to send email.

If you connect to a VPN, doesn't it's traffic bypass the local ISP's blocking of port 25?

We have tried telling Outlook to only send/recieve using the VPN connection.  We've tried creating client to gateway groups inside the router and using Greenbow and Shrewsoft's VPN client to connect.  We can connect, but still can't send.  We've enabled IMAIL to use an additonal port.  I notice when I do an ipconfig, the gateway always says the exact same as the IP address of the vpn connection instead of what the gateway should be inside the remote network.

Would making entries in LMHOSTS file make any difference?

I'm at a loss and would love some ideas from a different set of eyes.

Software/Hardware used:
Linksys RV042 Router, Greenbow VPN Client, Windows XP VPN Dial-up connection