I'm thinking of solving it by blacklisting outlook.com domain, so that senders at least know that I can't respond to them. I can put a message in the error response, that will be reliably relayed to the sender by the sending system.

Google's slightly better. Recently I did an experiment and created a few gmail accounts and sent some riduculously spammy messages full of typical keywords in between those gmail accounts, and they were all successfully delivered. Always.

Then I sent e-mail from new gmail account to my email server and simply responded and it went to spam. It's ridiculous that such a simple heuristic like someone responding to a message gmail user sends doesn't get the message through spam filters, even though the system can clearly determine taht the message is legit based on many variables (References field referencing message-id of the original message (noone else than the recipient should know this), reply being from a correct source (DKIM/SPF), message having normal looking business content, etc.).

There's way too heavy a weight on sending server IP range reputation.