Internet Explorer>Tools>Internet Option>Browsing history>settings and check your settings, especially the days which tells how much history you want to keep.
Not sure if you are still running CCleaner but you have to uncheck two options. History for one and index.dat the other. Index.dat does just what it says and indexes your history files.
Obviously if you're not running it then IE6 seems to be the problem.