I think your IP address issue can be an issue to any hosting provider. I have experienced that issue with a VPS from SiteGround. May I know what mail server do you install on Linode server?