I've built mail servers before Gmail existed that lasted long enough to get blacklisted by Gmail.

Fixing it was always pretty simple -- or at least, non-mysterious. They'd bounce some things, I'd look at the headers of the bounced messages, and therein were links to instructions there that showed how to resolve whatever issue it was this year.

Just follow the steps, implement the new thing, and stuff started flowing again in rather short order. Not so bad.

IIRC, the only time it ever cost us any money was when the RBLs started keeping track of dynamic IP pools and we needed to finally shift over to something actually-static.