I was wondering how such privacy sensitive feature can even be legally always on, however I did found in other discussion that it should be possible to actually turn this off in an user friendly way:
- Go to Settings.
- Select Privacy & Security.
- Choose Search Permissions.
- Scroll down to Web Search.
- Set "Web Search from Microsoft Bing" to Off.
I have not tested it yet though.