Outlook has the same searching issue. I often have to resort to manually eyeballing through my email archives to find what I'm looking for. Very annoying indeed.