Strange – using Gnome search, I couldn't find it any more. Now, I thought that this is how the usability experts think is the most efficient way to launch an application these days: open Gnome application menu, by slamming the mouse into the right hand corner, then abandon the mouse, and start typing the app's name using the keyboard. Really, it's so intuitive. But, anyway, I eventually got used to it.
I do see that its desktop file has 'nodisplay=true'. Removing that, restores 'software update' as a searchable app.
I'm almost afraid to ask WTF was that about, and whose bright idea it was.