Windows – Is it possible to keep Windows start menu search from accessing the internet

I have just set up a new PC with a fresh installation of Windows 10. The PC is connected to my company's network, and must make use of a proxy server to connect to the internet, because of company policy.

I have turned off Cortana in the settings, and also turned off Search online and include web results in the Cortana & Search Settings menu.

However, when I open the start menu and start typing, a dialogue titled Cortana appears asking for proxy login and password. If I cancel this dialogue, I can continue typing my search term, e.g. update, but no search results appear. The results box remains blank, not even the animation with the flying dots appears which indicates a search being executed on a properly working system.

If I search for the term update on my private Windows 10 machine at home, this search yields, among others, Search for Windows Update, Windows Update Settings, and files with the word update in the name, all local results.

As an experiment, I tried circumventing the proxy server, which results in the start menu search working as expected: It yields local results but not web results, as configured. If I turn the proxy server back on, the search continues to work until the PC is restarted, at which point search stops working again.

The same happens when I provide valid login data when prompted: Search begins to function and continues to function even if I uncheck the proxy login dialog's save credentials box.

At this point I could ask the person who will be using the PC later on to provide their proxy login to Windows and have the system save the credentials. However, it irritates me that they should have to do that, since I have explicitly turned off any start menu setting related to accessing the web.

Are there maybe some settings I have missed that will eliminate the need for Windows to access the internet when the start menu is used, or is this unchangeable Windows 10 behavior?