I just setup messenger & I am able to select "search archive", but I
cannot get any kind of queries to return any data. I see that the archive
data store is getting updated by conversations. I ran the repair on the
messaging agent archive for the heck of it and all was well.

Is there something I may have failed to turn on? I am using the default
policy and I have it set to archive sessions.