Ich bin mir ziemlich sicher, dass Ihr eine Security- Policy angelegt habt und dort die minimale / maximale Verschlüsselung auf einem Wert steht, der mit Euren neu registrierten Benutzern nicht übereinstimmt... Prüfe das mal (Keys and Certificates- Tab des Security- Settings- Dokumentes).
Dadurch wird automatisch ein Key- Rollover initiiert, was aber nicht immer sauber funktioniert (gibt es glaube ich sogar ein Hotfix für, hat evtl. was mit der Vault zu tun: Wahrscheinlich wurde die ID in der Vault angepasst, aber die ID am Client des Benutzers nicht)