First, let me say "Thank You!" for your timely article, which is just in time to help me with my next project. I do have one thought about your solution to searching on the value in an encrypted field. You state the issue as "We can't simply add a DecryptByKeyAutoCert(...) = @param clause to our WHERE clause and expect decent performance". This would certainly cause every record to be scanned and the field to be decrypted to determine if there is a match.
However, since the result of encrypting a specific phrase or sequence of characters will always return the exact same encrypted value, you reverse the issue: encrypt the @param, which will yield a value that you can directly compare against the stored values in the table. This only works when the WHERE clause is "=" on "IN (@ParamEncrypted1, @p=ParamEncrypted2,...) , and would not work for any other comparison, such as "<", ">", or in a "LIKE " clause. However, for fields like SSN or Credit Card numbers, this would be perfectly acceptable.
I admit that I have not tried this, but I don't know of any reason it wouldn't work. For example, assuming @param is declared as varchar(16):
--symmetric key approach; need to open the key once per session
open symmetric key MyKey decryption by certificate MyCert;
DECLARE @ParamEncrypted varbinary(68);
SET @ParamEncrypted = EncryptByKey(Key_GUID('MyKey'), @param)
select * from MyTable where EncryptedText = @ParamEncrypted
Again, thank you for your time in preparing this article. You have already saved me a ton of experimenting to see what might work. 