I've changed every reference to plesk.rackshack.net on my server and yet email headers still show plesk.rackshack.net (and subsequently most emails are not sent). I'm wondering if I would need to recompile qmail? I personally don't like rpm, but anyways, here's the actual email header (domains and ips are edited).

Return-Path:
Received: from plesk.rackshack.net (ns.ourcompany.net [207.44.*.*])
by *.spray.net (Postfix) with SMTP id 751E32512F
for ; Sat, 3 May 2003 07:48:23 +0200 (MEST)
Received: (qmail 15470 invoked by uid 48); 3 May 2003 06:06:59 -0000
Date: 3 May 2003 06:06:59 -0000
Message-ID: <*.qmail@plesk.rackshack.net>

There is a "sticky" field in the psa database table dns_recs that's written with the hostname as it was when Plesk was installed - it creates a PTR record that points back to this default hostname. Use phpMyAdmin (seperate install - not the Plesk one) to change that hostname (it's easy to spot because the Host field will be plesk.rackshack.net) and then just turn DNS off and back on again to rewrite the PTR zone for the server's base IP.

There's no way to change this from within Plesk, which assumes that you have used a real hostname for the server before you install Plesk.