Tag start menu search broken

Searching from the start menu resulted in no results Searching from the start menu suddenly stopped working on one of my machines recently. Only when it stopped working did I realise how much I had started to rely upon it…