Just got finished with Apple Support via Chat for this issue.
I think it’s fixed!
Turns out all that was necessary was a “Reset all settings” action (Settings → General → Reset). Something must have junked up the search settings in the past, and that issue was carried forward in every new setup because I always restored from a backup.
I’ll report back if it fails again, but it seems wholly solved. Woohoo!