Thank you for the suggestion, which I am sure will bear fruit down the track.
I ran the tool and it found and fixed (it said) 77 errors but, sadly, not the error in question.
Just in case, I moved a message from my Deleted folder to the faulty folder. The message immediately disappeared from sight, but was listed in a search, as before.
However I am just about to re-boot, in case that helps after the Microsoft fix