Not sure if this will help, however search works only from the Contacts app, not from Telephone app, not when adding contacts to the mail message. Only in Contacts you see the Search in Exchange icon on the bottom of the contact list.
Also data connection should be already active and "allow connection in background" must be set to ON. If those condition are not fulfilled icon is visible, but then you get "no data found".