JustaFew
Bincs has suggested the correct things to try however I will go over a slightly different way to do it which is usually faultless.
Close down all applications you have open esp IE.
Now if you have a big blue e on your desktop right click on it and go to properties now this is the same screen as you get in Tools - Options but sometimes works better when IE is closed
Now click on the Clear History button then the yes button - it should take a second or two depending on how much you surf.
Now click on the Delete Files button and then OK - again this may take a few seconds.
Now open IE again and see if this has cleared the list of previously viewed sites, Bincs was half right, it will only show you the sites you have physically typed in but will autofill any that you have previously visited.
If this doesn't work then do a search for a folder called History then delete the contents of it which will get rid of it all.
Let me know if you have no joy.