New IPs are often old IPs that have been used for other purposes before, and often blacklisted. Especially IPs on easily spun-up and spun-down hosts like DO. On DO, after every VPS I've removed, and then started up another a week later, it has a different IP. It would be easy for a spammer/phisher/whoever to abuse this quick address re-allocation, but hurts regular users.
One more point of data from my experience: I have never set up mail servers at hosting providers in remote datacenters, only local servers in my own server rooms which I could physically touch. I guess it’s quite possible that Gmail, etc. have figured out by now where all the IP blocks of hosting providers are, and are very suspicious of them.
Even when I used to work at HostGator and handled many of their abuse issues, they had many issues with being blacklisted just because RBLs didn't recognize new HostGator IPs or the rate of email being sent from their new gateways.
So, at least with my personal and professional experience, I can attest to the issues with using self-hosted mail servers.