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.
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.