I've had my mail servers at Linode for about 8 years now, no problems at all. If anything, I am more restricted on mail processing rules than anyone else.