Missing or invalíd password reset trust certificate

Every time I try to reset a password for a user (who has an id in the vault) I get the above error message.

I can see the certificates in the Directory and I have tried to recreate them - but no luck.

Subject: Password reset certificate is a special cross-certificate

You can create them using the ID Vault wizard. For already exising ID Vault, select the ID vault and then the option to “manage” it. You will be presented with several options, among them defining password resetters. This will create the password reset certificate.

Subject: Password reset certificate

The problem is, that I have created these certificates!

Do I have to create them for every OU-level? Or is the O-level enough?