unasked for pop-up "Windows cannot find 'C:\Program Files (x86)\Search Extensions\Client.exe'"

What has happened is that your antivirus or antimalware software has properly identified client.exe as an unwanted program and removed it.  When this happens, however, there are often remnants of the malware left behind that attempt to start the now-missing malware executable.

In your case, it seems that there is a scheduled task that is attempting to start client.exe.

• Click the Start Orb, type the following into the Search box and press Enter
      Task Scheduler
• When the Task Scheduler window opens, click on "Task Scheduler (local)" in the left pane
• Use the scroll bar at the right to scroll down to "Active Tasks"
• Use the inner scroll bar to scroll through the list of Active Tasks to find the one that is attempting to start Client.exe.  Look for "C:\Program Files (x86)\Search Extensions in the "Location" field
  
  
  
• When you find the entry that has Search Extensions in the Location field, double click it.
• In the right pane ("Actions") find "Delete" near the bottom of the list and click it.
• Close the Task Scheduler and reboot
• You shouldn't get the popup any more

If that doesn't work, or if you can't find the correct task to delete, download Autoruns --> http://technet.microsoft.com/en-us/sysinternals/bb963902.aspx

• Run Autoruns and after it completes scanning, confirm that the "Everything" tab is selected (it should default to that) then click File > Find and search for client.exe
• If a line with client.exe is found, confirm that the "Image Path" shows C:\Program Files (x86)\Search Extensions and then clear the checkbox at the left end of the line
• Press F3 to search for other instances of client.exe (I don't expect there to be any)
• Close autoruns and reboot
• You shouldn't get the popup anymore

If you used autoruns, once you are satisfied that the problem has been corrected and no other problem has been introduced, you can re-run autoruns and this time "Delete" the line with client.exe in it.

I suggest also using Windows Explorer to go to C:\Program Files (x86) and checking the contents of the Search Extensions folder.  If it is empty, delete the entire folder.  If files remain, they too are likely remnants of malware, but I don't want to tell you to delete them without knowing what they are.  If there are any exe files, use your favorite search engine to research the file names (or post the list back here).

I have run autoruns and deleted the client.exe entry but still I am getting the error on reboot.

Looks like you have similar situation like I had just several days ago.

In my case, I had a malicious program called Rocket Tab deleted just a day or so ago by my anti-virus.

I had nothing called client.exe in my computer, but using the Autoruns I found a thing with the Rocket Tab in the file name.

So my tip (though I'm an IT lame) would be you have some other file among the tasks, which is causing the window to pop up. It may be something with the malware name in the file name.

I would recommend you going one by one through all those yellow marked tasks in Autoruns (you'll also clean your computer of lots of rubbish, if you're so messy like me ;) my computer seems to be a bit faster after start up now) and delete everything that you think shouldn't be there.

Good luck!