Give the guys at MailGun a call or Email.. They are backed by Rackspace now, and have incoming/outgoing capabilities. They may be able to work something out for you
We use Sendgrid for Hostbill transactional mail, and Office 365 for actuall staff email. (Most people find this funny, since we are Google Apps partners).
Do you need to both send and recieve mails? Or is this just transactional use? I have had luck with Sendgrid and Amazon SES for sending out transactional email, since we have a separate helpdesk for incoming/outgoing queries.