W jaki sposób je zapisywać? Zwyczajnie do bazy danych? Czy macie jakiś inny sposób na zachowanie prywatności?

W bazie, sprawdzasz przecież własność.
ID | Użytkownik od | Użytkownik do | Treść.
Takie minimum..

Nie o to chodzi. To rozumiem.
Problem w tym że mój klient ma dostęp do bazy i będzie mógł czytać PM swoich pracowników

Pierwsze co mi przychodzi do głowy i chyba najłatwiejsze w podłączeniu base64_encode przy wysyłce i base64_decode przy odbiorze.

Nie stosowałem nigdy w praktyce ale myślę, że dobrym rozwiązaniem byłoby:
mcrypt_encrypt, mcrypt_decrypt.
base64 jest dosyć pospolite i rozpoznawalne.
Przy mcrypt stosujesz swój klucz, który gdzieś może być dobrze schowany, a w skrajnym przypadku także w jakiś sposób zaszyfrowany (base64 + eval, dzięki czemu żadnym IDE nie wyszuka deklaracji klucza).

Treść wiadomości można umieszczać w polu blob (binarnym), standardowo nie można ich odczytać (w nowych wersjach phpmyadmin można wymusić wyświetlanie, ale o tym trzeba wiedzieć).