You may have to directly delete the appropriate files.
Assuming you are using Windows XP, you may try the
following:
--
To delete the History folder and index.dat (XP)
Log on as Administrator and delete the desired <username>
folder and reboot.
(or log on as another user that has Administrator
privileges)
Example: "C:\Documents and Settings\username\Local
Settings\HISTORY"