Searching for the same phrase in DuckDuckGo, the 2nd result pointed to a Samsung forum thread [1] which, while pointing to doing things with a Samsung account, said it started working by itself in 1-2 days, which it did.
Setting aside the fact why Android would behave like that, the search results in Google were so low quality and awful... While this is just an anecdote, it seems for quite a few types of search results, their quality has dropped hugely. Is it due to people hijacking the results by using clever tricks? Or has Google's algorithm starting to hit some sort of limit in terms of the amount of content that needs to be indexed and ranked? I don't know. But something definitely seems off to me.
[1]: https://eu.community.samsung.com/t5/other-smartphones/my-pat...