Those typed stores are completely different. Are we getting confused yet? You will soon see why using one of the many "privacy" utilities is popular.
Remove IE Search History -- Line #24
Remove Google Search History -- Line #33
To do this manually for other search providers
Go to the key listed below:
HKEY_CURRENT_USER\Software\Microsoft\Protected Storage System Provider
Find the GUID for your Search engine. Google is:
S-1-5-21-1960408961-220523388-682003330-1003
Continuing, with Google as an example:
With the S-1-5-21....in blue, choose File/Export and save it to your deskop and name it googlehistoryclear.reg. Leave the registry open then go to your desktop.
Right click the saved reg file and choose Edit. If it needs an association choose Notepad.
Scroll down to these keys:
[HKEY_CURRENT_USER\Software\Microsoft\Protected Storage System
Provider\S-1-5-21-839522115-1708537768-1343024091-1003\Data\e161255a-37c3-11d2-bcaa-00c04fd929db\e161255a-37c3-11d2-bcaa-00c04fd929db\q:StringData]
[HKEY_CURRENT_USER\Software\Microsoft\Protected Storage System
Provider\S-1-5-21-839522115-1708537768-1343024091-1003\Data\e161255a-37c3-11d2-bcaa-00c04fd929db\e161255a-37c3-11d2-bcaa-00c04fd929db\q:StringIndex]
To make the search/scroll easier they are listed in alphabetic order and you are looking for the end of the string in this case \q:StringData and \q:StringIndex. So scroll down to the q's....
Under q:StringData
Highlight what is listed after the word "Behavior"= only up to the words "Item Data"= and delete it. Then place a - (minus sign) after the = so that it looks like this: "Behavior"=-
From there hightlight what is listed after the words "Item Data"= only up to the next key and delete it. Then place a - (minus sign) after the = so that it looks like this:
"Item Data"=-
Do the same for q:StringIndex.
Once done choose File/Save. Use the red X to close. If it asked to save again, answer yes.
Return to the registy and delete this key: (right click, delete, accept the warning)
HKEY_CURRENT_USER\Software\Microsoft\Protected Storage System ProviderS-1-5-21-1960408961-220523388-682003330-1003
Then go back to your desktop and double click your saved regedit, answer yes. Then open Google and the search history is gone.
The only difference with any other Search provider would be the GUID.
To Clear Google Toolbar History
Click on the Google logo to access the drop down menu. Choose the Clear Search History option. This will clear all the previous searches out of the drop down box.
Source for much of the above: Kelly Theriot