Pyss off on Firefox...
The problem isn't that he's using IE.
The problem is that he's deleted his history.
Windows doesn't delete the history without user-directive first. In other words, he told Windows to delete the history from IE. It's his own fault if it's gone (which it is, btw).
There are only a couple ways to remove the history from IE. You can delete it by command in the Options dialog. You can use Disk-Cleanup to clear it away. You can have it set to automatically delete old history after a ceterain length of time. And you can fk around with the registry and remove the history that way. You can also delete the history from within the user's profile directory.
If this happened because of a disk-cleanup proceedure, the dialog provides several ways of finding out exactly what you're getting rid of (namely the "Details" button right on the dialog box).
In short, this is not application error, this is user error.
There's no real way to get the history back once it's gone.