The right click search functionality is part of the explorer shell. Use a File Manager replacement or Search replacement and you should be ok. Another option is to open the search bar manually and then pick the PC from there. Works AOK here.