550 sorry, no mailbox here by that name

I'm getting a strange error on certain email addresses I send to, I'm using Outlook 2003 on Vista and as soon as I click send, almost instantly I get the following error:

Your message did not reach some or all of the intended recipients.

      Subject:      Website
      Sent:      01/05/2009 11:04

The following recipient(s) cannot be reached:

      'enquiries@*******.co.uk' on 01/05/2009 11:04
            550 sorry, no mailbox here by that name (#5.1.1)

Now this mailbox definitely exists as I can send using my email account in a web based program.

The strange thing is I get the email almost immediately after I've clicked send, it goes to the outbox, disappears and voila this email is in the inbox, it's as if it never even leaves the server!

The email comes from System Administrator and has a strange circular icon in Outlook with a red arrow? I'm not using Exchange or anything like that, 9 times out of 10 emails will go without a problem.

Thanks in advance.

Chris