The network your IP is in makes a difference. My mail server is currently at OVH, which is a good enough neighbourhood for Mailjet to have built an email business there.
I very occasionally have an email bounce back (once a year or less). The bounce message typically includes information on exactly why it bounced and how to contact the receiving server's operator to figure it out.
The vast majority of the work goes into the the initial setup, which takes an evening if you're using a packaged mail stack. [1]
[1] If you want a free packaged mail stack, here's a FOSS one: http://www.iredmail.org I have no experience with it but have heard good things.
I went through the whole rigmarole of reverse-DNS and SPF. I also started very gingerly in the beginning -- for a few weeks it was no bulk emails and trying to mostly email personal contacts. But I've never had any trouble until now.
Google will complain about deliveries if you don't have IPv6 records. Everything else: DKIM, SPF, etc is optional and helpful.
Simple greylisting works wonders to block incoming spam.