Windows XP Pro – Delete Search History

I am running Windows XP Professional currently. I discover I could not permanently remove the search history, which I have keyed in before. Whenever I restart the Internet Explorer, the history came back in the search box. How should I get it removed permanently?