As someone who has run his own mail servers since 2000, and still gets his email delivered to people's spam folders (even when I've emailed them in the past, or simply replied to their original message), this is very interesting, as I always enable plaintext outbound email.
Your symptoms sound exactly like the issues I was having - everything was "right" (in theory) - emails were leaving on the right IPv4, that had the correct PTR, etc etc. I just couldn't figure out what was wrong.
It was the same issue - even replies to existing threads had the issue. What got me looking into it more closely was that I had no issues delivering to G Suite tenants; it was only issues with 365 tenants.
I wonder if there's a non-trivial correlation between people choosing to genuinely self-host their own mail, and those who use plaintext outbound mail by default (and know what that means).
I'll have to give this a try. Thanks for the tip!