Die Standards PGP und S/MIME arbeiten alle hybridmäßig. Die E-Mail werden mit einem zufälligen symmetrischen Schlüssel verschlüsselt, der vorher über die asymmetrische Verschlüsselung auf beiden Seiten bekannt gemacht wird. Das die symmetrische Verschlüsselung zu unsicher ist, ist doch Quatsch. Lediglich der Schlüsselaustausch muss hier sensibler vonstatten gehen.
S/MIME ist bei Outlook zu bevorzugen. Das ist schon fest in Outlook implementiert und funktioniert mehr oder weniger gut. Für PGP müssen in jedem Fall Addons nachinstalliert werden.
Das würde ich nicht mal im privaten Bereich einsetzen. Das GPGOL-Addon sorgt dafür, dass Outlook langsamer startet und gerne auch mal hängt. Des Weiteren ist das für den unerfahrenen Benutzer nicht komfortabel und nicht einfach zu verwalten. Das Produkt an sich hat m.M.n. auch gar nicht den Anspruch in einer so großen Enterprise-Umgebung zu "dienen".
PGP lizenziert nach Clients in Staffelform (umso mehr Clients, umso günstiger wird es pro Client). Bei so einer großen Anzahl wie du sie hast, würde ich direkt dort anrufen und nach einem Angebot fragen.
Bevor du hier anfängst irgendwelche Produkte anzufragen, würde ich mich zunächst mit den gängigen Verschlüsselungstechnologien (S/MIME und PGP) auseinandersetzen. Da gibt es nämliche gravierende Unterschiede bzw. Vor-/Nachteile, die zu beachten sind. Die Benutzung von bspw. S/MIME zieht noch einen langen Rattenschwanz an Arbeit/Kosten mit sich, wie z.B. eine PKI, Zertifikatsgenerierung für jeden Anwender oder ggf. Kosten für nicht-selbstsignierte Zertifikate. Es muss auch beachtet werden, ob zukünftig mit externen Unternehmen verschlüsselt kommuniziert werden soll.