Hello Eric. I tested this in our production system and was not able to replicate the issues you're reporting. My assumption here is that there may be an indexing issue, or that the messages themselves include some encoding that prevents successful searching. Can you submit a support ticket on this so we can take a look?
Kyle Kerst
Lead Internal Network/System Administrator
SmarterTools Inc.
smartertools.com