I took a look back at the stuff I put in my overkill anti-caching CGI headers, and you have all that except for the Last-Modified header. Maybe adding that will help?

IE at the very least is known to be rather… idiosyncratic about its decisions to use or not use a cached copy of a page, though — including cached copies of some headers.