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?