It turns out that you will NOT get a search button with Exchange (it actually runs as IMAP/WebDAV) but you will get a search button if your server also offers ActiveSync.
I had this issue and I was shocked to see that there was no search button with Hotmail, knowing that it does offer Exchange functionality.. I figured I won't be able to search my work e-mail too (when I set it up), anyway, finally I got my work e-mail activated and the little magnifying glass appeared. Now I can search. But the stock e-mail app is so weak and missing features, I immediately installed touchdown and started using it. It is not as fast as native e-mail app, but it has all the features you would need.
I suggest trying 3rd Party e-mail apps.
Not being able to search combined e-mail box is another huge problem. Coming from BB where you can literally do anything you want with any number of boxes, makes Android look very outdated and lacking. But you can get around it with some extra expense and a bit of hassle (running add'l app, battery and storage issues, etc..) otherwise it is OK. (I think google wants everyone to use gmail, hence there are far more options with gmail compared to native client)...