Che io sappia (e ne ho riprova da questo forum) max-width funziona in tutti i browser moderni, con l'eccezione di IE quando lavora in modalita` retrocompatibile (quirks mode).

Ma se la DTD e` Strict, IE lavora in modo standard.

L'unica altra alternativa che vedo in base a quanto hai detto, e` un errore di sintassi. Prova a farti un giro dai validatori: validatore HTML e validatore CSS.