Есть некоторое количество пользователей, часть из них пользуется TheBat, часть Thunderbird. Возникла необходимость использовать PGP шифрование обмена почтой между ними. Можно ли это как нибудь сделать?

gnupg AFAIK можно использовать и с Bat и с TB.
Только я не знаю есть ли к нему какой то графический фронтенд для управления ключами. Я из командной строи это делаю.

Есть.
http://enigmail.mozdev.org/
http://pgpru.com/manuals/enigmail/