Do the students take the laptops home? if not can you not just put a blocking program on the school network? I do think it would be better to achieve this actively rather than in a passive manor.

I can't find anything about a backup directory for IE history, probably because the developers couldn't see why they needed to create one.

You could try something like this (i have never used it but it seems to fit the bill): http://www.everstrike.com/lock_folder.htm you may be able to stop them deleting the file - but then i don't know if IE can still write to it.

At the end of the day, being a student myself, I know - there is always a way round anything an admin puts on to your pc. Especially because all they need to do is use a proxy and then you won't be able to track it at all.