I’ve been struggling getting Windows Desktop Search to index my emails. It just doesn’t do it. I’ve found lots of people with different issues, but none of them worked, until I found a forum that referenced http://support.microsoft.com/kb/927676. Turns out, if you’re running Windows Desktop Search, Outlook AND Exchange System Management tools on your computer, the Exchange tools overwrite a DLL file that enables searching. To fix simply run %windir%system32fixmapi.exe, reboot and reindex.
Google is a wonderful thing.