I have been having this same problem since upgrading my system to Vista 64bit and Office 2010 64bit, and been trawling the internet looking for answers. Just as I was giving up after trying every suggested answer I found, I discovered the answer on my own.
My email is through an Exchange Server, and in the Account Settings - More Settings - Security the option to Encrypt Data between Microsoft Outlook and Microsoft Exchange was checked, and then in the Search Options - Indexing Options - Advanced, Index Encrypted files was unchecked. This made me think to myself "can Instant Search not index my emails because they are encrypted?".
I removed the check from Encrypt Data between Microsoft Outlook and Microsoft Exchange, and then rebuilt my index.
I am now able to find indexed emails in my Exchange Email folder, with Cached Exchange Mode Selected.
I have not tried it the other way round, i.e. Leaving a check in the Encrypt Data between Microsoft Outlook and Microsoft Exchange, and then adding a check in the Index Encrypted files option. But this may also work.
Hope this helps anyone that has been scratching their heads over this.