Plesk rejects all mail after crash

[Polaris2203]

Following a power failure plesk now rejects all mail. Incomming mail returns to sender with the following error:

(IP and domain altered to protect the innocent...)

This message was created automatically by mail delivery software.

A message that you sent could not be delivered to one or more of its
recipients. This is a permanent error. The following address(es) failed:

[email protected]
SMTP error from remote mail server after RCPT TO:<[email protected]>:
host hobby.net [67.123.82.107]: 550-(divine.flexihostings.net) [67.123.11.124] is currently not permitted to
550-relay through this server. Perhaps you have not logged into the pop/imap
550-server in the last 30 minutes or do not have SMTP Authentication turned on
550 in your email client.

The server accepts mail coming from another local machine (192.168.1.5) but is rejecting all mail from the WAN. Even setting relay to open makes no difference!

Accepted domains (rcpthosts) in Qmail includes all the domains, and I can't see anything that is wrong.

dnsreport.com reports that it is able to connect to the mail servers, and network-tools.com reports that the server acknowledges the email addresses are valid.

One final note - prior to the crash, one client was getting this error on a number of his email accounts, and now it is affecting all domains.

Any help or ideas would be most appreciated, as clients are getting a bit upset about this.

Pete