原因はわからんけどDNSがらみの何かじゃないかな？
俺も以前DNSでMXを見てリレーするようにしていたんだけど、
DNSサーバが不調の時におかしな動作をするので
LUSER_RELAYとLOCAL_RELAYを指定して強制的にリレーするように変えた。