Find Related Messages Not Working

[katm3]

I am using Outlook 2013 in cached mode.

I also have full access to my boss's mail/calendars etc (set up with full access on the server).

Previously I could click on a message he had replied to (from his inbox) and click "Find Related Messages" and it would find all messages across all folders that were part of that 'conversation'. (see screenshot)

However, now I cannot do this, it just says "We cannot find what you are looking for". I have the search function set to "all mailboxes" but this changes nothing. I check for the replied/forwarded email in sent items, and it is definitely there, but this [Conversation]: search is not working.

It appears to work correctly in "online" mode, but this is so incredibly slow to use on a day to day basis that it is not feasible.