Even email is no longer really decentralized. Google and a few other email silos now make up the bulk.
Gmail considers anything beyond big corporate email providers as second class participants - and so does the other big providers.
I've used one of the many blacklist check websites to test my domain and only ended up with two false positives which I've rectified through their web forms.
It was mostly smooth sailing from there.
Note that this is using a dedicated server as a host, a while ago I tried the same thing from my home ADSL (with a static IP) and that was a pain since those "home" addresses are generally blacklisted by default since people tend to assume that emails from those addresses are sent by compromised computers.
Nowadays I know many ISPs even block port 25 by default so that's not even an option anymore.
This may not apply if you are a low volume sender.
But if I were running email for any new organisation I wouldn't have that luxury ofcourse - I'd have to pay for a Google/outlook or other major provider account - or spend a lot of time "reversing" the reputation of the ip/ip block my dedicated servers had - and as none of the major providers provide a simple check like rbl etc - it's a frustrating guessing game where your test-mails to your own Gmail(etc) account go through, but mail to new senders is silently dumped to the spam folder.
I don't mind greylisting, mail bouncing or blacklisting. It's the magic "intelligent" filtering which is annoying - because the only indication of error is that you don't get a reply - because your recipient haven't seen your mail.
In a way it's worse that it's rare - you never know if you've fixed the issue, or some arcane combination of your sending configuration and email content (an email not in English?! Probably spam!) will mean a new recipient will never see your mails.
We've been running on the same domain+IP for over a decade. Hotmail block us when we're whitelisted by the original sender and also responding to an email and also have corresponded before. We've never sent even a multi-person email never mind spam, always as a response to an enquiry, very low volume.
We're blocked apparently because Hotmail has an intermediate level warning on a sender domain on another IP address managed by the same ISP; we were un-blocked before but they now say they won't allow our email through - we have SPF but can't work DKIM with our shared status. The only silver lining is they actually responded inside a fortnight to tell us that they're going to continue blocking our [at most] once a week emails to our customers who happen to have hotmail/live/outlook addresses ...
To work around I made a live.com address to send through for customer who use MS email. ~4 days later they started blocking it from remote access ... something like not enough direct website logins for the amount of IMAP lookups (a single client checking every hour or so during work hours). Few log-ins seemed to fix it.
We can pay to have the spam service MS use whitelist us though, apparently.
You have to accept and work with changing expectations.
If you are unable to relocate to more reputable hosting, and your messages are legitimate, solicited, authorised, well-formed transactional email (no promotional mail shots), I suggest you switch to delivering through a squeaky-clean provider like Postmark.
They could just obey their own customers white-listing, or over-ride blacklisting for domains that act appropriately.
So you really think that having a domain of 10+ years standing that doesn't send unsolicited emails at all is "not behaving like a first class citizen"?
If someone in your ISPs /26 sends spam from a different IP and using a different domain, that totally means you're a massive spammer who's ruining the internet??
I could of course change ISP but which of the 15+ yo ISPs will have a spammer somewhere in their IP block, no way to tell.
So the only option left is pay to be able to send email to MS addresses. And you're fine with that? It's all our fault for replying to emails?
Your expectations don't match reality and you seem to prefer complaining to change.
I have basically no sympathy at all, I'm afraid. It is your fault, not for "replying to emails" but by failure to update infrastructure as the context changes. This is your problem to fix, and it appears you've made poor choices in that direction based on a misattributed sense of entitlement.
But how is such an effect not an issue? It makes it hard to "elevate" a box at home to a proper mail server, and makes it hard for new generations to host their own mail (until an ip6-only world (and probably also then) all new users will need to recycle old ips).
As for dmarc, I'm still not entirely convinced it's a great solution to smtp/spam issues. Dkim is already annoying enough if you occasionally want to send mail through/from a different smtp - like Gmail if you don't run your own webmail.
These days I'll always take a paid service over a "free" one where I'm the product.
Ultimately I'd love to host everything myself. But, at present, I don't have the technical knowledge to trust myself to secure everything.
On top of that, on an even more emotional level, the principle of myself being the product doesn't sit right with me.