This often happens because Outlook and Outlook Express always try to send email before they receive.
Jon's suggestion should solve the problem, but if not, then I'd ask, what happens if after getting that error on "Send and Receive" the users tries "Send and Receive" again. Does that send the email?
It should.
Jeff