Si se me permite, corregire unos detalles:
Código HTML:
<div id="header"><!--(lo llamas header en el CSS)-->
<ul>
<li><a href="#">menu1</a></li>
<li><a href="#">menu2</a></li>
<li><a href="#">menu3</a></li>
<ul>
<span class="random"><script de imagen aleatoria>...</script></span>
<form .....>....</form></div>
Código:
#header {width: 100%;
height: 150px; /*por ejemplo*/
background-image:url(logo.jpg);
background-repeat:no-repeat;
}
#header ul {/*el menu, los position:relative no son necesarios.*/
width: 60%;
float: right;
}
#header li {display: inline;
}
*/#header img {todo esto lo pongo como comentario, el logo es parte del layout, por lo tanto no debe ir como contenido.
position: relative;
float: left;
margin: 5px;
}*/
#header a {
color: black;
text-decoration: none;
}
.random {
}
form {
}...
De resto debe funcionar bien.