Only Custom Objects that have a tab that is set to Default On or Default Off appear in search results for that profile.
Set up your Search Layouts and add columns to filter.
Yep, setting up Search Layouts for each object is time consuming and fiddly, but worth it for the end user's benefit.
Help Notes https://help.salesforce.com/HTViewHelpDoc?id=customize_searchlayout_notes.htm&language=en_US
This is a handy help topic on examples of Lookup Filters https://help.salesforce.com/HTViewHelpDoc?id=fields_lookup_filters_examples.htm&language=en_US
I always forget how to do Enhanced Lookups. I find them cumbersome to set up.
- Go to Search Settings and choose the objects to have Enhanced Lookups
- While you are there choose the objects to have Lookup Auto Completion
- On your object that has Enhanced Lookups enabled go to Search Layouts then Lookup Filter Fields.
- For Contacts choose Phone, Mobile, Email and any Member Number or Unique Identifier you have.
- While you are there also set up Search Filter Fields.
- Set it up on Accounts and Contacts or any custom object that you add to records by lookup frequently.