pana hay varios errores en tu codigo como por ejemplo el uso de dos div sin necesidad aqui te hice un codigo nuevo sin esos errores que tenias
Código:
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="es">
<head>
<title>tile</title>
<style type="text/css">
body{
background:#000;
}
#menu {
background-color:#000;
float:left;
width: 100%;
margin:0px;
padding:0px;
list-style-type:none;
}
#menu li{
display:inline;
}
#menu a{
float:left;
width:auto;
text-decoration:none;
text-align:center;
color:#ff0000;
background-color:#f7f8e8;
padding:3px 5px;
}
#menu li a:link, a:visited {
text-decoration:none;
background-color:#0000FF;
}
#menu li a:hover{
background-color:#FFFFFF;
}
</style>
</head>
<body>
<div id="menu">
<ul>
<li><a href="that.html">Nuestra Compañia</a></li>
<li><a href="this.html">Nuestro Datacenter</a></li>
<li><a href="that.html">Planes Hosting</a></li>
<li><a href="theOther.html">Planes Reseller</a></li>
<li><a href="theOther.html">Registro de Dominios</a> </li>
</ul>
</div>
</body>
</html>