[unluckier]

You have to block outbound communication for "Search" in the Windows firewall. Regardless of whatever privacy settings you may have set.

[vetinari]

Yes, I know.

I was trying to point out, that even when you disable everything using the provided controls, the OS still doesn't respect your choice.

Be careful regarding the searchui.exe firewall rule. It names specific assembly version - one silent update (is there any other in win10?) and your rule is invalid, instead a new rule that is enabled is suddenly in effect.