Ok, it seems that relaying for that particular IP is not setup. I'm not sure how it is in Plesk but in qmail there's a file called 'tcp.smtp.cdb', where you can define the IPs to relay. The error you're getting could be due to that. Read about that
here. (The second question.)
For Plesk, you could try what the second poster mentioned
here.
I've seen that you've already tried the Plesk forums, with no help.
Maybe if you ask something along the lines of "I've seen this error and I may have to setup relaying, as per
DJB's site. Could someone tell me how?", you might get a response.