Me acabo de dar cuenta que es el DOCTYPE!!!! oO
Aun sin el html, head, body, etc, me funciona:
Código HTML:
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<style type="text/css">
#menu li ul{visibility:hidden;}
#menu li:hover ul{visibility:visible;}
</style>
<ul id="menu">
<li><a href="#">menu1</a>
<li><a href="#">menu2</a>
<ul>
<li><a href="#">submenu1</a></li>
<li><a href="#">submenu2</a></li>
</ul>
</li>
<li><a href="#">menu3</a>
</ul> Pero borrandole tan solo la primer línea, ya no hay forma de que funcione.
PD: ¿No sería mejor usar un display:none y display:block? Queda un espacio en blanco, y no se si así se quiera, pero yo no lo veo muy atractivo =P