In tools-Internet options is the history set to zero days? Could someone have reset it to hide their tracks?
History is stored in an index.dat file, this may have become corrupt. If this is the case then you should delete it and let windows create a new one. Browse to C:\Documents and Settings\UserName\Local Settings and delete History and Temporary Internet Files folders.