It seemed to be working for a few hours.. emails were searchable by all methods (Windows Key + F, Instant Search, Explorer). Then suddenly, the index, itself, lost all of the emails - ie/ the index now does not contain any emails (Outlook items are still checked in Indexing Options).
I am going to rebuild the index yet agains, but it is really perplexing.