The only thing I can see is that when you use the search icon, it uses the existing windows explorer window, if you use the right click menu search… it calls the search function and opens it in a different window.

I know when I tried to replicate what you said (using context menu), I thought I had the same problem as you as it did take a while before the new window opened.

Perhaps that path (linked to the context menu) is not finding the search function and not reporting an error.

Perhaps a check of the event viewer logs (after an attempt) and see if an error is being recorded, it might give a clue?