Searchable/Sortable Database Fields with MySQL/PHP

Greetings, I need to securely store lots of sensitive contact information and notes in a (MySQL or other freely available) database that will be stored on a database server which I do not have direct access to. This database will be accessed by a PHP application that I am developing. However, I also need to be able to search/sort these data with the database functions (SELECT, ORDER BY, etc) so simple PASSWORD style encryption of specific fields would not work. (For example, I need to encrypt contacts' names, but need to be able to sort results by name). (I realize I could load the entire table into memory with PHP and process/search/sort it there, but that's obviously not a very good solution). Ideally I would like to encrypt entire tables. An encrypted file system is not really an option, because the goal is to prevent loss if the database server is hacked (in addition, I wouldn't be able to install an encrypted file system on the database server). My sense is that this is a difficult problem. However, I made the mistake of promising this functionality, so I'm scrambling to figure out some kind of solution. Any suggestions? Thanks so much! Matt