Some customers are currently experiencing a problem where they cannot search for messages or messages searches are incomplete. We are looking in to the cause of this and will update this post when we know more. Sorry for the inconvenience.
UPDATE 06:00 AM CET: After restarting associated back-end services we believe this problem is resolved.