I mentioned it's my personal email, not really meant for work (though I did use it for that also).
But technically yes, if they choose to trust Google with delivering the email and Google doesn't deliver, it's a problem on their end. Setting up your email in a way that a particular service (in this case Google) accepts it, doesn't scale.
How do you contact family and friends who aren't savvy enough to setup their own email server? What about replying to job interviews? It would really suck if you didn't get the job because the hiring manager never received your email.
aaand nearly all of them have an auto reply response with a contact email or page where you can "unblacklist" your ip easily
I've submitted this fix to RFC-Clueless several times over the past few months, but it's abandoned. Every request times out after a few weeks. Great, we're on a blacklist whose raison d'etre is "blacklist those not following the rules", and the bastards don't even follow their own declared workflow.
Been there done that. Takes a good while to build up reputation, but it's possible, even without dkim signing or anything like it. Also since it's my personal email, my policy has always been "if you can't receive it because of your mailserver, sucks to be you -- you're using that service so it's on your end."