Well, I've figured out my particular issue, hopefully it will help someone else.
A couple years ago when I originally installed Office 2011 for Mac, I was not happy with the location that Microsoft chose for storing my local mail database, inside my Documents folder: "~/Documents/Microsoft User Data". As a result, I moved the "Microsoft User Data" directory into ~/Library/ where I thought it should belong, and created an alias (symlink) in my Documents folder to point at the new location.
Since I knew that Outlook uses Spotlight indexing for it's search, I had a hunch this was a Spotlight indexing problem.
This morning I shutdown Outlook (and killed the Microsoft Database Daemon that runs in the background), removed the alias in Documents and moved the "Microsoft User Data" folder back into Documents, after which Spotlight started indexing the folder. After about 45 minutes, search was working again in Outlook.
So it appears that with the Mavericks upgrade, Spotlight stopped indexing "~/Library/Microsoft User Data", and by moving my email database back into "~/Documents/Microsoft User Data", Spotlight indexed my email again. There could be other ways to fix this, but I haven't investigated further at this point.