What name have you put in the external e-mail server name field ?

I find that you need to just put the server name (i.e. not the fully
qualified domain name) for it to work  as our system seems to append the
domain name because of our network card settings - bizarre but true

Also, you may have relying turned off on your server

To test if you are allowed to send  e-mails log on to the appropriate web
front end - open a command prompt
Type

telnet emailservername 25

press return

If you do not see a welcome message you're e-mail server isn't even
accepting connections from anyone but a predefined list and so you
should speak with your exchange  / mail admins !

If you do connect then type
helo
Press return - you should see a welcome message - you may have to enter
helo mydomain.com if it insists on knowing your domain - if helo fails
try ehlo (ehlo is the extended form of helo) - once you've seen the
extra welcome message type
Mail from: youremailaddress
Press return
RCPT To: youremailaddress
Press return
Data
Press return
Subject: This is a test mail from MOSS
Press return
This is a test mail
Press return 3 times
Enter a period / full stop
Press return
If you can get all the way through that then you should be able to relay
so repeat by swapping out the address above for the one you've entered
in moss as a from address and try again

If it goes through I'm at a bit of a loss but that's what you need to do
to check that you have basic mail flow - personally I fully expect it to
fail at which point  you can ask your exchange admin people to allow
relaying from the MOSS WFE as you will know and be able to show that
relaying isn't turned on

I have tried just the server name, and also the
domain name. I followed your instructions  below and they completed
successfully (The mail seems to have queued successfully).
However, I did not actually receive the test email  in my Exchange
mailbox - I also tried sending to just a regular email address (not
Exchange) - no luck there either.

Additionally, this is the error we receive if we try to add a user:

"The following users do not have e-mail addresses specified:
[username]. Alerts have been created successfully  but these
users will not receive e-mail notifications until valid e-mail
addresses have been provided" Then there is a link to "Set my e-mail
address..." And yet, if you click there, it only gives a link to
attach a file.

Any ideas?