Thanks for your reply. I tried what you mentioned, however, if I just have the domain in there and leave off the hostname, no mail is sent out at all.... Instead I've removed everything from /etc/mail/local-host-names and it's a bit better.
I've also edited the /etc/hosts file so that it's
xxx.xxx.xxx.xxx myhostname mydomainname.com
I had some other garbage in there that was mucking things up. It's still not working properly, but that's not the sendmail problem on my box, it's a problem with the relay it's going through.
Thanks for your help