A feature available since Exchange 2007 and Windows Mobile 6 is the ability to search your entire Exchange Mailbox from your Windows Mobile phone.
(Ref. http://blogs.technet.com/b/exchange/archive/2007/05/28/3402914.aspx)
#TheMissingFeature Microsoft, where is Exchange Mailbox Search for Windows Phone 7?