If you possess a BlackBerry and use the built-in Messages and Contacts apps, its now much easier to search emails and contacts on your device by using the new version of Google Mobile App.
Just enter your query, either by text or voice and Google Mobile App will search through all the emails and contacts available on your device and present you with all the relevant emails/contacts. You can then call that contact or do a quick reply to that email.