Order-Preserving Encryption Revisited [pdf]

Recent password db leaks and considerations around storing HIPPA data in the cloud had me thinking about encrypted data in RDBMs.

Given the limitations that seem apparent, I am wondering more about whether the correct approach is to encrypt/decrypt everything client-side and only store encrypted data. Your client gets hosed at some data point, particular once data size gets big, for some definition of big, since it has to handle all the data munging.