I eventually fixed it.
In my case I concluded that it was something to do with one of my accounts because the issue only occured my one of my three Outlook accounts and impacted two independant machines in the same way.
I did two things;
- Went to the impacted microsoft account settings online and navigated to Privacy where under Browsing and Search you can clear your search activity history. This didn't immediately fix the problem, other users seem to find that it can take quite a while to synchronise.
- I then went to Outlook search options and modified the indexing options to deselect all selected locations (including outlook)
Not sure which of these cleared the problem, but it is OK now. BTW - the issue seems to be related to Outlook being unable to retrieve details of search history from central servers because in my case if I disabled internet connection the problem also went away while the connection was unavailable.
Unfortunately switching to the 'new' outlook didn't help me because it doesn't support search across multiple mailboxes - who knows if/when this and support for .PST files will be added?