I just switched email service provider from Google apps to a VPS with a Hong Kong host. Now I find a huge part of all outgoing emails ending up in spam boxes and in some cases getting totally rejected by receiving servers. I've set up SPF records, rDNS and all of that, but it seems a lot of European clients' mail servers are just not fond of mail from HK.
We're based in China so everything even remotely Googlesque works terrible which is why I switched in the first place. Also, we have a lot of people coming in for short term projects so I ideally wouldn't want to go back to the $5/month per user solution.
I'm not sure what would be a good solution, any input is greatly appreciated!