Exim Problem: Sender address rejected: need fully-qualified address

My mail log returns the following error when sending email to a gmail account: Sender address rejected: need fully-qualified address

Here is the full error message:
2010-10-08 03:44:58 1P4214-0007MM-NL <= alleart@V100723TU7C41-1 U=alleart P=local S=527 2010-10-08 03:44:58 1P4214-0007MM-NL ** dettehusker@gmail.com R=smart_route T=remote_smtp: SMTP error from remote mail server after RCPT TO:<dettehusker@gmail.com>: host smtp.ultrahosting.com [74.213.174.254]: 504 5.5.2 <alleart@V100723TU7C41-1>: Sender address rejected: need fully-qualified address 2010-10-08 03:44:58 1P4214-0007MP-Rm <= <> R=1P4214-0007MM-NL U=mailnull P=local S=1556 2010-10-08 03:44:59 1P4214-0007MM-NL Completed

Exim is set to the folowing relay:

@ROUTERSTART@
smart_route:
driver = manualroute
domains = !+local_domains
transport = remote_smtp
route_list = * smtp.ultrahosting.com

The server is running CentOS and Exim 4, the email is sent using PHPs mail() function.

Thank you for your time and effort

From serverfault John

• It looks like this is the address the server is trying to use to send mail: alleart@V100723TU7C41-1 and it's being rejected. You may need to specify a valid email address in your php.ini file, or request a change through your hosting provider.

  John : Hmm yes V100723TU7C41-1 shows as hostname in SSH. Do you know how I can make it dynamic for each domain on the server?

  Force Flow : The address needs to point to a valid SMTP server. Do you have qmail installed on the server? Can you point to an external SMTP server or mail relay?

  John : The server uses mail relay. Dont think I have qmail, its running Exim. Details of my mail configuration can be found in my other question http://serverfault.com/questions/188840/configrue-exim-sendmail-for-relay

  John : I only needed to change the server name from something else than the default generic one. Thank you for your help mr Force Flow or is it Clark Kent
  From Force Flow