Launch Windows Explorer, select the Organize button at the top, select folder and search options, select the search tab, check the first three items in the How to Search area. (which would include "natural language search".) Ok and close out.
Click Start, type partial 8563.
What was the result?
You can also click Start=>type index in the search box, select indexing options from the program results and adjust the the items to be index and re-index the computer. This will take a while. The mail files should be in C:\User
Name\My Documents\Outlook files for 2007 and 2010 versions.
The sooner you forget XP the better off you will be. I adapted to issues like this with Vista, so Win 7 seems ok. I am able to find what I want. I keep an XP machine for whatever reason and view it like something from the Smithsonian