I managed to get the search selection back, analogous to this thread on XDA (for the SetupWizard).
$ adb shell settings delete secure selected_search_engine
$ adb shell pm enable com.google.android.apps.setupwizard.searchselector
$ adb reboot
Tried it a few times on a FP4 that had already gone through the selection and could reliably change the search provider after a reboot. If you are running root be careful though, the search selector really doesn’t like to play nice with Magisk, I didn’t manage to get it to work on a rooted FP4.