Can't be sure, and forgive me if this is already what you mean by disabling "Internet Search", but I suspect you are experiencing this because of Bing's involvement in the start menu search. To fix it, you have to regedit some stuff:
https://www.reddit.com/r/Windows10/comments/f09184/how_to_bl...
I had to use the registry key as well because MS broke the GPO (I would say on purpose but anyone who is in a position to mess with GPOs knows how to edit registry keys with it as well) but it really does get rid of it for good.