There have been several posts with users having problems deleting the history in IE6. I don't know whether this will help, but I've managed to solve the problem on my PC. The problem seemed to start when I installed the 832894 MS security patch in February.
Later on, I installed a correction to the patch. This correction didn't mention a problem with the history, but has allowed me to delete the history without problems.
The reason I had to install the update's update was because I couldn't use my online banking after installing the first update. If people have problems with secure sites, or deleting history, it's worth installing the update.