I just started getting this message this message this morning.
550 5.7.1 <receipient email address here>... Relaying denied: You must check for new mail before sending mail.
I did a check of various forums but none of the fixes really related to my particular problem. They are mostly informational about SMTP which I already knew and dismissed as being a no brainer. Howeve, I did get a hint from one forum that suggested it might be an error generated by the ISP requirement.
I went into my OL2003 email account properties > Outgoing Server > put a check mark in "My outgoing mail server (SMTP) requires authtentication".
This in itself wasn't unusual however what I did next was activate the radio button by "Log on using" and then entered the UN and PW my ISP requires to use my account. THAT was highly unusual. HOWEVER.....it did solve the problem.