Sounds like you are running x-cart of a windows server, is this true? If not under general settings of the cart do you have use the Internal PHP mailer enabled? Are you using sendmail or another product for sending mail. Have you edited the email templates at all or are they still default ones?
Also if you ARE using a windows server, please read the FAQ found in the members area (
http://www.x-cart.com/wmembers.php).
hth.
