Hi Zen.

My guess is that the database has not re-encrypted existing records that have not been accessed or amended. Might be worth checking with Salesforce support to see if they can force all existing records to re-encrypt on deterministic encryption.