@Lexz It's still not clear from your posts, so far, when this problem started on your servers;
....on all Plesk servers we run without changing te configuration.
^^ Explains
where it is but not
when it started.
Is it, since you very first started using Plesk? Or, only since you made a recent OS or Plesk update? Timewise, there's no point of reference, at present.
You've also mentioned a test above, that you use, but didn't post any further details of that test (method and/or results). That means, that there's no visible example yet, of the problem(s) that you're having and/or any links to the test sites that you've used to get those results. So on here, it's all still
unseen, at present. You have breifly described it, in your opening post (
...don't have a valid certificate on ipv6 in their mailclients...) but that's a generic description really.
If you can run some basic SSL / DNS pre-checks before your next post, that would rule out any simple IPV6 config errors prior to looking specifically at mail?
You can post the test results on here, if you want. Just edit/remove your own server details in advance, if needed.
You can quickly test any of the domains that you are hosting, on any of your servers as follows:
HERE If you are using IPV6 and the domains are configured correctly, then you'll receive two different reports - every time; 1 for IPV6 and 1 for IPV4.
HERE If you are using IPV6 and the domains are configured correctly, then you'll be able to validate the AAAA records plus any other DNS data that you wish
HERE If you are using IPV6 and the domains are configured correctly, then you'll be able to validate the IPV6 addresses in the MX Test section (and other tests)
These are only simple SSL & DNS tests, not specific mail process tests, but they are useful, advance external views of some of your basic IPV6 config. There are many other, more detailed IPV6 specific tests that you can run (later - if needed) but those above, would give a much clearer idea of the starting point...
You could also test the specific domain or sub-domain that you're hosting Plesk on, on each server, too; If you're going to advance double-check everything.