E` un bug noto, che in IE il padding e` interno alla larghezza/altezza degli oggetti, mentre negli altri browser e` esterno. Dipende dal diverso box-model adottato.

Questo non si verifica in IE6 se usi XHTML Strict, che potrebbe quindi essere un modo per sistemare il tutto (se hai usato un linguaggio HTML che si presta ad essere upgradato).
Altrimenti devi rivedere il layout, facendo in modo da adattare le cose ai due brwoser.
Oppure fai un CSS specifico per IE, da linkare all'interno di commenti condizionali e che corregge le impostazioni per IE.

Trovi riferimenti per tutte queste tecniche tra i "link utili" del forum CSS.