Applw Mail with MS Exchange 2003 - Receives but won't send.

I am trying to use Apple Mail 2.1 with our MS Exchange Server 2003. I have
entered all the account details and can receive mail without any problems
but when I try and send it's a different story.

When I send a mail to someone else within the company the Activity Viewer
shows that the mail is delivered to the Exchange server and the mail goes
from the Outbox. However, the mail never reaches the recipient.

When I send a mail to somebody who isn't within our domain I get the
following error message:

Cannot send message using the server
xxx.xxx.xxx.xxx (Exchange IP Address)

The server response was: 5.7.1 Unable to relay for
otheruser DeleteThis @outsidedomain.co.uk

Use the pop-up menu below to try a different outgoing mail server. All
messages will use this server until you quit Mail or change your network
settings.

Message from: Me

I get three options, Edit Message, Use Selected Server and Try Again Later.
I just press try again later as I know the address is correct, and I only
have one server to try. So the message just sits in the outbox and trys and
fails again later.

In Activity Viewer, It gets as far as 'Delivering Message - Sending
Recipients'.

In Connection Doctor everything has succeeded and is lit up green.

I really don't understand the server response about being requested to relay
for otheruser DeleteThis @outsidedomain.co.uk I have tried to send a message to that
address not relay for it.

Can anybody give me any ideas as to what I'm doing wrong as it's got me
stumped?

Many thanks in advance for your help.