You guessed it right, it's another logged-in users bug. Meet isolated (and I don't mean ReHIPS isolated here, just running from a user other than logged-in user) Outlook and broken All Mail Items search. This search is based on Windows Search service and it doesn't work with the service disabled. And Windows Search doesn't index user files, if the user isn't logged-in. It means broken search.
This issue was found several months ago, it wasn't fixed then. I haven't checked it since, but I suspect it to remain broken for many years to come.