Hola, Jamati.
A la primera cuestión, podrías no quitarle el borde y pintarlo del mismo color del fondo: div.menu ul li {border-bottom: 1px solid #D00;} Es un bug de IE6, que los li son problemáticos, y con un borde se reduce su tamaño.
A la segunda cuestión, podrías no dar altura al li.inf, sino hacer tu imagen de 10px y colocarla dentro: <li class="inf"><img src="tu_imagen.jpg" /></li>
Prueba por ahí, a ver qué tal.
Mikel.