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...