Thanks a lot for this, I spent the weekend trying to fix this and I'm still waiting to hear anything back from my first Microsoft support ticket raised (radio silence for a couple of days now) so great to see we were not the only one with the issue.
We raised a second support call and was told that it was an issue with a recent Edge update, however, I have a couple of InTune setups and only one of them is having the problem, our Group Policy based machines do not have the issue either. All these machines are running Edge version 98.0.1108.56.
I am testing the change to the short version of the search URL https://www.google.com/search?q={searchTerms} and search seems to be working as expected now. We are using .co.uk at the end as we are UK based. As mentioned above in @Noel Burgess post, I imagine using the full URL will give you regional search results but this is not important to us.