Hola Mikmoro !
Gracias por decir que plantee bien la pregunta, una imagen vale mas que mil palabras ¿no? ... 
Respecto a tu solución, decir que si funcionó, aunque yo ya probé esa opción pero no sirvió en su momento, de todas formas seguro que la aplique mal.
Gracias, y ahora adjunto como queda el tema.  
 Código HTML:
 <style type="text/css"> 
  #menu { list-style: none; margin: 0; padding: 0 } 
  #menu li { 
      background-image: url ( fondo_x.gif);  background-repeat: repeat-y; 
      padding: 4px; 
  }
  #menu a { text-decoration: none; margin-left: 2%; }
  .imagen_left { margin-left: 1%; vertical-align: middle; }
</style> 
<ul id="menu"> 
  <li><img class="imagen_left" src="icono1.gif" alt="" /><a href="" title="">Texto 1</a></li>
  <li><img class="imagen_left" src="icono2.gif" alt="" /><a href="" title="">Texto 2</a></li>
  <li><img class="imagen_left" src="icono3.gif" alt="" /><a href="" title="">Texto 3</a></li> 
</ul>  Firefox: 
 
I.Explorer (version 6) 
 
Saludos!