Microsoft 365 features that help users manage their subscriptions, account settings, and billing information.
After some back and forth with Microsoft Support I now have a solution:
I had to export the certificate path certificates (see screenshot in original post) as .SST and import that one. Although I had tried that already before I guess that I hadn't correctly published the personal certificate via Outlook or hadn't waited the right amount of time after publishing.
Now it worked immediately (in OWA and the iOS app) after importing the path.sst - no waiting time at all.
Edit:
Also, to check if the correct certificates have been uploaded you can use the following commands (writes to c:\temp):
$sst = (Get-SmimeConfig).SMIMECertificateIssuingCA
$certs = New-Object System.Security.Cryptography.X509Certificates.X509Certificate2Collection
$certs.Import($sst, $null, 0);
$certs
$certs | % {Export-Certificate -Cert $_ -FilePath C:\temp$($_.subject).cer}