You could also check the IE cache file. However, if he is smart enough to clear the history and documents, then he is probably also smart enough to clear the cache. Still, it wouldn't hurt to look.
If you don't find anything, can you restrict his access to the comp? I don't know if you can restrict access enough to prevent him from clearing the history, cache, documents, etc using NT, 2000, or XP. There is always a keystroke logger. However, it would have to run in the background.
Ryan