I've noticed users have problems searching custom fields in lookup views. Actually it does not have anything with custom fields.
In a lookup view search is performed only on columns displayed in the view. Even if you add a column to "Find columns" list, you still have to add it to "Displayed columns" list.
So if you want to find a Contact by his, let's say, birth date, you have to modify Contact's lookup view to display birth date and add the birth date column to "Find columns" list.