I've run a mail server, and still help out with one, and getting consistent deliverability is hard. We've wanted to move to another hosting service for years, but the only reason we're doing ok right now is that our dedicated IP has a solid history and we just can't give that up in a migration.