1. While in Internet Explore, go to Tools, then Internet Options.
2. After clearing the history like you did before, set the Days to Keep pages to history to 0.
3. Go to the Content tab and press the AutoComplete button.
4. Remove the tick on web addresses and press apply.
If you want to remove other traces...
5. You may want to clear the Forms and Passwords too and disable the other ticks if it is relevant.
6. And also go to the Advanced tab and make sure 'Empty Temporary Internet files folder when browser is closed' is ticked.
Stuart.