Airmail is able to search for contacts in the Global Address List of Microsoft Exchange or Google Apps.
By default this setting is disabled and needs to be enabled for the specific mail account.
Enable Global Address List
1. Tap ≡ the menu icon in the top left corner on the app, which will reveal the menu.
2. Tap on the Google Apps or Microsoft Exchange Account
3. Tap to enable Google Address List. If enabled, the button will be green.