I had problems with MS (Hotmail/Live/Outlook/whatever they're call it now) when I changed hosting provider which I traced back to the hosting provider owning an IP that had in the past been associated with spam (that for-real is what I was told) -- that seemed a bit over-zealous to me.

As it wasn't possible to pre-check IP addresses (it wasn't blacklisted, and in any case the email was being served from a different IP to the one that was apparently previously an issue) for any particular hosting company - and I could only afford cheap hosting - then I decided to relent and made an Outlook online account and sent the mail from that.

It seemed totally crazy to me to reject mail from a 15 year old domain that sent at most 30 emails to Outlook per month, _always_ in replay to an email; SPF/DMARC were set AFAIR and whitelisting the email address from within my own 20+yo hotmail account didn't make any difference, MS still wouldn't let _me_ receive the emails. Like if your user says the email address is fine, and sends an email to that address, .. then perhaps you should allow the user to receive that one email??