other8026 Thanks, that's very useful to know. If it is an generic Android 15 issue, then I can hope they will (eventually?) fix it as more people start complaining. (I don't have developer options enabled; I seem to recall I turned it off immediately after I installed grapheneos, without changing any settings except oem unlocking.)
Do you happen to remember any specific apps you encountered? If you notice any more, please update here. If any of them are open-source, then I could find out what caused the problem and how they resolved it.
In the meantime, it seems opening their website in a browser on my phone allows access to search so, although it is very tedious, that is a workaround for now.