Will Honeycomb get an update to add email search (Xoom)?
To address your question in the comments: Star this issue and perhaps leave a comment. Hopefully Google will take notice and improve the email app!

In the meantime, though, I do suggest using a third-party app.  Depend on your company's rules, you could even create a secondary Gmail account and either have your work emails forwarded to it or have Gmail grab mail from your work account via POP3 or IMAP, and then you could use the Gmail app for search.