You shouldn’t have to explicitly trust it even once (if you did, it would be no better than a self-signed certificate).
Are you sure that the mail server is sending the intermediate certificate? If the mail client program can’t follow the chain all the way to a trusted root, that could cause this problem.
(However I don’t know how to fix that with Plesk specifically).
I realised what I did. I was using the server SSL to secure the mail server and then the domain for the host. This caused the trust problem. It’s now resolved.