With RIJNDAEL encryption, this is problematic because like you say you have decrypt in the database to be able to search, you may want to see this thread at stack overflow.
http://dba.stackexchange.com/questions/23908/how-to-search-a-mysql-database-with-encrypted-fields
to be honest, i think it is a little over board to encrypt columns like first or last name.
I can see encrypting the street address, that is a lot more personal than the first and last name.
when it comes to encryption, it shouldn't be applied as a blanket for the entire disabuse, but used sparingly on data that is truly private, and you need to weigh tradeoffs like the ability to search,