There's a much better solution than either Jon Schneider's or phwd's answers that involves adding an internal "second name" to the contact.
I have a number of contacts that have names using non-ASCII characters, that I prefer to look up using their ASCII equivalents but have the non-ASCII show in the To: field (for instance, I want to type "Katya" to find "Квтя" so I don't need to change keyboard layouts just to look up a contact). You can make Gmail do this currently by using the "Merge Duplicate Contacts" feature, and though I've seen zero documentation on it I've been doing it for a couple years now without issue:
First, create a duplicate contact, but with the nickname as the actual name. Then, use the "Merge Duplicate Contacts" feature to merge them, setting the actual name of the merged contact to the one you'd like to see in the To: field. This leaves you with a contact with a hidden "second name", that can be used for autocompleting and in searches.
A downside of this method is that the second name field, as far as I can tell, is truly hidden and unchangeable — you'll have to delete the contact and create a new one to get rid of it. But luckily, most people don't change their names very frequently, so this hasn't been an issue for me. I also typically set the "nickname" field to the hidden name's value during the merge, as a record what the hidden name is.