Ok, togliere la div intermedia mi piace, ma è sbagliato usare visibility:hidden; per nascondere la span, dato che, a meno di non avere impostato anche overflow:hidden;, usare il visibility;hidden; implica che la dimensione dello A venga dilatata se il testo è più lungo, e non credo che questo sia ciò che si voleva:

<span>testo link</span>

a.nav {background-image:url(off.gif);display:block;width:xxpx;height :xxpx;}
a.nav:hover {background-image:url(on.gif);}
a.nav span {display:none;}

Ciao!