Igotalife, some versions of IE (I think this includes the most recent one) do not clear the autocomplete list when clicking on "clear history". You know - the list that comes up as you type something in the, say, google search box. A file called index.dat can store that information. So I guess the best way is for you to go to google and click inside the textbox and browse through the search terms for something strange. This is obviously assuming the person used google. I know it's a stretch, but the only other way I would be to recover the deleted history file and that is extremely hard to do.
Another thing you could look at is "Microsoft's really hidden files". When you delete the temporary internet files, some actually remain in a very well hidden location. It is pretty hard to take these files out, but they do contain information about where your browser has been. Here's a txt file about deleting (and maybe looking through) them: