You’ll have no luck with floated elements. They don’t obey vertical-align.

You need display:inline-block instead.

http://cssdesk.com/2VMg8

Beware!

Be careful with display: inline-block; as it interprets the white-space between the elements as real white-space. It does not ignores it like display: block does.

I recommend this:

Set the font-size of the containing element to 0 (zero) and reset the font-size to your needed value in the elements like so

ul {
    margin: 0;
    padding: 0;
    list-style: none;
    font-size: 0;
}
ul > li {
    font-size: 12px;
}

See a demonstration here: http://codepen.io/HerrSerker/pen/mslay

CSS

#wrapper{
  width:400px;
  height:auto;
  border:1px solid green;
  vertical-align: middle;
  font-size: 0;
}

#left-div{
  width:40px;
  border:1px solid blue;
  display: inline-block;
  font-size: initial;
  /* IE 7 hack */
  *zoom:1;
  *display: inline;
  vertical-align: middle;
}

#right-div{
  width:336px;
  border:1px solid red;
  display: inline-block;  
  font-size: initial;
  /* IE 7 hack */
  *zoom:1;
  *display: inline;
  vertical-align: middle;
}