Android端末から自社メールサーバーを使ってメールを送信しようとしたところ、SSL証明書のエラー(PublicKey has changed since initial connection!)が出て送信できませんでした。

自社メールサーバーは無料のSSL証明書発行サービスLet’s Encryptを使用してSSL化しています。
Let’s Encryptの証明書は有効期間が90日であるため、2ヶ月ごとに自動更新するようにしています。

そのため、Android端末に最初にメール設定して(initial connection)から、長くても2ヶ月経てばPublicKey has changedとなる訳です。

解決策をGoogleで探してみると、見つけたのがこの記事でした。
確認してみると、確かにサーバー設定(受信/送信)のセキュリティの種類は「SSL/TLS(証明書をすべて承認)」になっていました。
「SSL/TLS」に変更して解決と相成りました。