Pues max-width debería de funcionar sin problema a partir de IE7. En IE8 puede dar problemas al combinarse con overflow auto/scroll.
http://caniuse.com/minmaxwh
Supongo que el problema vendrá de otro sitio. No tengo IE instalado así que no puedo probar.
