Delete Browser History but still visible in Search

I have deleted the Browser History - no problem doing this - History shows as empty.
But when I use the Search application, I can still see all the browser history!
The only way I can delete this is to remove the battery. There must be a better way!
Any suggestions please?

Have you tried this:

On the Home screen, click the Browser icon.
Press the Menu key.
Click Options.
Click Cache Operations.
Click Clear History.
Press the Escape key.

Make sure you select cookies as well.

that worked for me thanks