Hacker News Reader

As of a week ago, I was on Notes at work, which had not-so-great search. I still did this. Once or twice in the past few years I had to go in an delete large attachments, but I do that when it becomes a problem. It's not worth the mental effort of categorizing emails. (And deleting counts as categorizing.)

Now I'm on Verse (http://www.ibm.com/social-business/us/en/newway/), and it has great search. I'll keep doing what I was doing, just with even less pain.

What about something like OfflineIMAP + notmuch or mu? That works for me, and search is as good (or better) than it was for me using Gmail.

Not all Exchange setups are configured to allow IMAP access...

Sounds like you just have an incompetent IT department. Storage is cheap and fast searching of databases is a solved problem.