We use eWAY, couldn't be happier.
If you are going to push volume through there, ask them for some custom pricing:
http://www.eway.com.au/Contact/RequestQuote.aspx
While we don't use WHMCS for ticketing (currently using Kayako), we've got all our emails going through Google Apps and connect to each of 12 IMAP mailboxes every 5 minutes via cron, and have never had an issue with the connection being refused.
With is the case with both the free edition and the partner edition.