"Entire Message" search disabled / grayed-out in Mail.app

The Apple discussion forums are full of people complaining about
Mail.app being naughty and not allowing to search by "Entire Message".

I've also wasted some hours trying to work around this when it
inflicted me, with no luck.

Until, finally, I tried merely restarting the machine and vóila! It
was back...