Assuming for a second that it's not a hacking or rogue script problem, a few things to check to see if something in the configuration is hung from a previous install or something. And this is assuming you're on a Dedicated machine and not a VPS.
1. Have you run the
hostname command on the server to make sure it answers correctly?
2. Have you checked
/var/qmail/control/me to make sure it lists only the correct hostname?
3. Have you done a PTR lookup of your IP(s) to make sure something old isn't in the EV1 DNS? You can do this at
DNS Stuff. The PTR lookup is in the top righthand box. Note that to do a reverse lookup the address needs to be in .in-addr.arpa format. So if the IP address you're looking for was 12.123.234.3 you would plug 3.234.123.12.in-addr.arpa in the form box.
4. Lastly, realize that Qmail and pretty much every other mail server uses Reverse Lookups to get the information you're seeing. This can be troublesome when utilizing Name Based Hosting, because there is the potential for multiple domains to trace back to the same IP number. It can become more troublesome if all of the domains on a certain IP number have their own PTR record in their DNS.
If the domain in question were one on your server that was sharing the IP with other domains it's sometimes possible to remove the PTR record of all domains save one on that IP number and Qmail should use it. Of course this means the mail header would be correct for one domain and incorrect for all others on that particular IP number, but if it happened to be the main IP number with a domain set up to only be the hostname it's better than nothing.
Nighthawk release a reconfigurator tool that's here on the forums somewhere to make sure the hostname, /control/me, etc all match your server's hostname. But there is one place it cannot change. In fact, this same place is something you can't see or change from within the Plesk control panel. It's in the PSA database.
This isn't really a plesk bug. It tries make some assumptions and to do the right thing, which can of course lead to such problems. Basically this is what happens...
When Plesk is first installed it creates a PTR record in the PSA database that will
always write the first record in the reverse zone file to refer back to the server's name at install time. Which makes complete sense. The problems comes in when the server was built with either a "generic" name (eg plesk.rackshack.net that EV1 uses for all installs) or some other domain, which sounds like may be the case with your server. Even when you later set up the server under a real domain and fix all of the hostname issues this (now faulty) information appears in the PSA database so gets written to the reverse zone.
How can you tell if this is possible the problem?
Via ssh go to /var/named/run-root/var where the zone files are kept. Do an ls to look for a file that is the first three octets of your server's IP number range in the reverse in-addr.arpa format. Pico or Nano the file to read it.
Does the offending information appear in this file? If so, it means the original Plesk install has stuck the info into your PSA database.
How to fix it? Well, this is not for the faint of heart and it won't do you any good trying to change it in this file because Plesk will simply change it back. The fix requires directly editing the PSA database, and Plesk doesn't give you a way to do this. Like I said, not for the faint of heart.
You would need to install phpMyAdmin and log into the PSA database. (Make sure to put it in a
very safe place and I don't recommend leaving the install there after things are fixed! Far too risky.)
Typically, the first install data is going to be in record ID 2 in the psa database table dns_recs. If what you see there isn't correct, change it. Personally I would recommend using the server's full hostname, assuming you've got a PTR set up for it with the EV1 Reverse Pointer tool.