This is has been going on for a couple months now, and we've had almost no luck fixing it. We are running Yosemite 10.10.2

Basically any search in Outlook 2011 immediately give a "No Results" message. Using the same term or phrase in Spotlight proper finds relevant messages, and I can open them after some tweaking. 

Here's what has been done so far

1. We've completely removed the account and uninstalled Office 2011 according to the instructions found here . 
2. Reinstalled office and re-added the account. After allowing time for indexing still saw the same result.
3. Removed preference files for outlook and rebooted.
4. Had Spotlight re-index the entire drive.
5. Tested search under a different identity - same result.
6. Tested search under new user - Same result.

Does anyone have any suggestions?