FW機能を一時停止にされましたか？

ＰＣ再起動、アカウント再作成以外には何もしていないのでしょうか。
ウィルス対策ソフトやスパムメール対策等が引っかかることがあります。

エラーコードでざっと検索をした所、どうやらファイアウォール周りの問題っぽいですよね。
まずは、送信先の相手方が何か設定変更をしていないか、確認をしてみては如何でしょうか？アンチウイルスソフト等の機能で、何か制限されているのかもしれません。（定義ファイル更新のタイミングで、ある日突然発生しますよね）。

月並みですが、まずはこの辺りから。

環境がわからないので答えにくいですが．．．

メール送信先：同一ドメイン内
と言われますがメールサーバは同一セグメント内（ＬＡＮの中）にあるのでしょうか。それとも外部のプロバイダでしょうか。　外部のプロバイダでしたらＦＷがかまされていると思うのでコメント（３）さんの可能性がありますね。

昨日までは正常に送受信できていましたが突然メール送信ができなくなりました
ということは受信は出来るのでしょうか。外部の人からメールを送ってもらって受信できるかどうか　ということも原因究明に役立つと思います。

このような場合にはいろいろと試してみて「これとこれは出来るけど、このことはできない」というように現象を明確化すると原因が絞れます。

送信ポートは25番利用してませんか？
ＩＳＰが順次25番ポートでの送信受付を停止していますので
多分それが原因ではないかと思います

弊社のお客さんも一時期よく電話かかって来まして、大体原因は
それでした。

ＩＳＰとメールサーバー提供業者との組み合わせにより詳細の対策は
異なりますが、
弊社の場合
送信ポート変更：　25　----> 587
送信認証　ON
で解消出来ます。