建議你先用Yahoo、Gmail、中華電信....所提供的信箱測試，mail的問題有時牽涉的範圍很廣，甚至有時候也可能是對方的問題，建議先多方測試及交叉比對，先把問題範圍給縮小，比較有助於後你後面解決問題

你可能需要查一下mdaemon的smtp log,先確定一下,那個所謂的第一封,有沒有留下任何的smtp相關記錄,如被伺服器因XXX原因拒絕,或網路連線timeout或等等...
如果完全沒有,那代表完全沒有連線進來或在建立smtp session前,就被伺服器給拒絕掉了,如:有設定DNS反查或RBL等等..
還有對方是否有收到他們自己伺服器的退信,如果方便問的到的話!!
因為第二封信是可以寄進來的,所以代表mdaemon的smtp service應該是沒問題的,建議可以查一下外部DNS的設定,如:DNS註冊的Server Public IP,其每台DNS的Service及相關的記錄都是正確的.

我也曾經遇過類似狀況，後來查證SMTP & POP3 LOG無此紀錄後，反查USER怎麼會知道第一封信對方有寄你沒收到，USER回說 "另一個同仁有收到，他的信件上收件人上也有我的EMAIL ACCOUNT，可是我卻沒收到這封信"，之後查看另一個USER收到的信件，確認對方寄來的是對方公司列管的機密文件，只准提供給正本收件人，其他副本收件人對方的MAIL SERVER一率不寄送，在我的LOG上另一個同仁的收這封信的狀況也是正常的。所以還是建議您先查詢相關LOG後再來判別這個異常狀況的歸屬原因，才能對症下藥。

不知是否願意，應該考慮換一套 MAIL系統了
推薦一下:
MX Mail Live Key :
提供電子郵件系統、網頁式郵件、管理維護、LiveCD光碟內建OS作業系統、免安裝設定
LiveKey ISO檔案，支援虛擬化與異地備援服務
郵件備份稽核審閱、垃圾信件過濾、網頁伺服器、FTP、LDAP、DHCP、自動鏡射備份…等功能
內建 ClamAV 防毒系統
內建SpamAssist，圖像辨識、灰名單、線上黑名單資料庫