SBS 2003 – SMTP: 504 Need to Authenticate First

I currently have SBS 2003 using DNS to route email. Currently I have a 1/3rd of our emails being returned for error: 504 need to authenticate first. I have completed the steps in Microsoft’s knowledgebase and regarding authentication. No improvement. Any idea’s on what else I can do to correct this issue?