you may want to look at
http://forums.whirlpool.net.au/forum-replies-archive.cfm/896965.htmland
http://support.microsoft.com/default.aspx?scid=kb;EN-US;934709says exchange 2003 borks on greylisted addresses from time to time. That hotfix doesnt look like exactly the issue though..