This seems to get more bizarre by the minute...
There are two email addresses in the control panel - one in Registration Settings, one in General Settings... what are they? Are they valid email addresses for that server?
Is the board on Unix or NT? Sendmail or SMTP?