I think it's likely you're not properly authenticating to the outgoing
server, but without you posting the exact message and including your Outlook
version and account type, it's just a guess.
A virus tore up my system and I re-installed everything from a to z. Before,
I never checked the 'authenticate...' box on the set up. It is Outlook 2003
(SP2). Version 11.yadayadayada....