At first, I tried the way you mentioned via Options within the browser. Then I tried to do a memory clean followed by running desktop manager to see if I could 'Delete Selected Data' off of the device but couldn't find any history. I did a battery pull too. The browser history was cleared in the browser but not the main search from the home screen. Finally I tried an ALT-SHIFT-DEL and once it rebooted, the history was gone. So I'm guessing the history was actually cleared but the main search holds a separate cache until restarted? I'm not sure but it's a bit strange how that is holding on until that occurs. Didn't work with the battery pull but it did when I did the ALT-SHIFT-DEL? Very strange!