If you go into your inbox, you should have a magnifying glass at the bottom along with the new mail icon, folder select, refresh and options. The magnifying glass will let you search your emails. Not sure why the main Google Search function will not search emails, but I have used the search function from within my Corporate Exchange Mailbox. The search is not perfect, but it seems to search within emails, subject lines and email addresses.
Hope this helps.