Hallo,
erstmal danke für den Tip.
Zu meinen Problemen habe ich auch eine Lösung gefunden.
Eventuell auch für andere interessant:
1) Es muss auch in der Group Policy der jeweiligen Clients aktiviert werden, am besten über die Domain Group Policy.
Zu finden hier:
"Richtlinien öffentlicher Schlüssel"
2) Ja, man kann nach Punkt 1, auch einen noch "gültigen" Schlüssel mit dem gleichen priv. Key neu austellen.
Die 3. Frage ist noch offen. Vielleicht kann mir da ja jemand helfen.