Thanks Bob, that's fixed it.
You can't start up in DOS mode, but I was surprised to find that you can change the attributes on those index.dats and they stay changed.
Sure enough, IE created three different index.dats (Local Settings\Temp\Cookies, Local Settings\Temp\History\History.IE5, and Local Settings\Temp\Temporary Internet Files\Content.IE5) before finally giving up.
I also set Local Settings\History to read only. IE history seems to be sourced from multiple places, as you might expect from such a convoluted, over-engineered, poorly designed product.