Why removing float:left affects dimensions of a li element?
The cod is simple:

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
 <head>
 <meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
  <title> Horizontal menu </title>
<style type="text/css">
*{ 	margin:0;
	padding:0; }
.menu {
	list-style-type:none;
	margin:50px;
}
.menu li{
	display:inline;
	font-size:18px;
	line-height:36px;
}
.menu li a {
	float:left;
	margin:0 7px 0 0;
	text-align:center;
	width:100px;
	height:36px;
	color:#008080;
	text-decoration:none;
	background:#ffe8ff;
	border:1px solid red;
}
ul.menu li a:hover {
	color:#c60000;
	background:#a4ffff;
}
</style>
 </head>

 <body>		
		<ul class="menu">
		  	<li><a href="#">About</a></li>
			<li><a href="#">Servises</a></li>
			<li><a href="#">Solutions</a></li>
		</ul>
 </body>
</html>

You have assigned display linline in LI tag, though its not supported by IE browser. At first to solve that add float left to LI tag along with display inline. And after that you can remove float left from A tag.