I have at least one friend with a Gmail address associated with a fake name. In my contacts list, I have the correct name associated with the email address. I can then type this person's name in the recipient field and Gmail populates it appropriately. However, if I search this person's name in my email, their messages are not returned.
A workaround is to type "from:[start typing in the person's name and their email autocompletes]" and search for emails from that email address. However, this is unsatisfying if the person uses multiple email addresses, as I would have to look up each email address. Additionally, I might just type the person's name in and forget that Gmail isn't returning all messages from all of their email addresses, since some messages are returned.
