I had wordpress 2.2.2 hosted on FastHosts? and wasn't getting any email notifications, everything was landing in dead.letter. After some investigation I found it was because the phpmailer->Sender wasn't being set. Fasthosts check the sender email address to make sure it's a valid email address for an account in your domain as part of their spam filtering rules.
If you add the line
$phpmailer->Sender = "wordpress@" . preg_replace('#^www\.#', '', strtolower($_SERVER['SERVER_NAME']));
to pluggable.php on wp-includes before the line
$phpmailer->FromName = "WordPress";
I found this fixed the issue.