And what do you know... I post the above this morning and now it's no longer working. No Plex results appearing in Assistant searches at all. This had been working since I got the Shield and enabled Assistant a couple of weeks ago.
At the same time, I noticed that pressing directions on the remote would no longer allow repeating (scrolling) on long-press.
After a restart of the box, scrolling behavior was back to normal but still no Plex results in search. So off to Settings, then "Google" and finally "Searchable Apps" - Aha! Plex was showing as turned OFF. Which is insanely strange because I had been in this setting screen earlier today and saw that Plex was ON and at the same time I turned ON PBS. Now both were off.
Turning Plex back to ON seems to have resolved the issue - now we wat and see if it turns off again by itself in the future.