In 10 v1511 there is a new entry in the start menu search called "device search history" that is enabled by default.

I use

[HKEY_LOCAL_MACHINE\SOFTWARE\Policies\Microsoft\Windows\Windows Search]
to disable Cortana and Online Search however I cannot find a setting to disable device search history. Anyone know of how to do it? Thanks!