Using classic Outlook for Windows in business environments
Does this happen when you send a message directly (i.e. a new message, no reply) or just when replying?
Generally speaking, it's up to the recipient's email system to decide how messages from Microsoft 365 are processed. They can outright block them, perhaps due to the service being abused by spammers, and there's nothing you can do about it. That said, in most cases you can ask the recipient to "whitelist" your address, which can help delivery in some cases. They can also ask open a ticket on their end to get this looked into, if appropriate.