Exchange (in this case Office 356) mangles PGP encrypted messages when sending. Content-Type: multipart/encrypted; boundary="nextPart6734939.BlDrd8uHN9"; protocol="application/pgp-encrypted" ends up as Content-Type: multipart/mixed; boundary="_003_2390612FqyDRV8H2nlinuxe202susede_" And so KMail is unable to show the mail correctly. By editing the content-type to say multipart/encrypted, it's displayed correctly. See also https://gitlab.com/enigmail/enigmail/blob/master/package/fixExchangeMsg.jsm#L224 how enigmail deals with this.
Some more information: Messages are not garbled if only signed. GNOME Evolution also had the discussion regarding a workaround some time ago: http://gnome-evolution-general.1774414.n4.nabble.com/Evolution-3-18-5-2-Encryption-with-GPG-from-Hotmail-Account-message-structure-td4665706.html I also got Office 365 SMTP working. Their SMTP server does not have the problem.