Try using Opera (http://www.opera.com)
or use Mozilla / Firebird (http://www.mozilla.org)
Both of these have simple privacy deletion routines and will clear your history just fine.
If you prefer to stay with IE then perhaps a search in google (http://www.google.com) will help.
I just did a look on: clear history in IE
There were many helpful articles.
Good luck,
