Outlook won't send encrypted email to outside contacts

Check which Encrypt you're picking. In Outlook the Encrypt button has two flavours: the normal Encrypt (Microsoft's message encryption) and Encrypt with S/MIME. The normal one is built for external people. They get a message with a link and open it by signing in or with a one-time code sent to their email. S/MIME only works if you already hold the other person's certificate, so to outsiders it fails, which matches what you're seeing with internal people being fine. If you're definitely on the normal one and it still bounces, that's the admin. The tenant can restrict who encrypted mail goes to, or have a rule blocking it. Forward them the bounce message, the error text in it tells them which.