The following registry tweak is supposed to prevent users deleting history in IE. Insert usual disclaimer about registry editing not being for beginners here.

[HKEY_LOCAL_MACHINE \ SOFTWARE \ Policies \ Microsoft \ Internet Explorer \ Control Panel]
"History"=dword:00000001

[HKEY_CURRENT_USER \ Software \ Policies \ Microsoft \ Internet Explorer \ Control
Panel]
"History"=dword:00000001

If the second key doesn't exist, ignore it.