I have my personal e-mail on linode for probably 15 years or so and haven't had any issues with e-mail delivery (knock on wood). Had the same two static IPs there for years, and have always had things locked down so I couldn't be used as a relay for spammers.