You can do this quite easily with display table and display table-cell.

#wrapper {
width: 400px;
float: left;
height: auto;
display: table;
border: 1px solid green;
}


#right-div {
width: 356px;
border: 1px solid red;
display: table-cell;
vertical-align: middle;
}

EDIT: Actually quickly messed around on CSS Desk for you - http://cssdesk.com/RXghg

ANOTHER EDIT: Use Flexbox. This will work but it's pretty outdated - http://www.cssdesk.com/davf5

#wrapper {
display: flex;
align-items: center;
border:1px solid green;
}


#left-div {
border:1px solid blue;
}


#right-div {
border:1px solid red;
}

The only downfall of my modifications is you have a set div height...I don't know if that's a problem for you or not.

http://cssdesk.com/kyPhC

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;
}
  

I realize this is an ancient question however I thought it would be useful to post a solution to the float vertical alignment issue.

By creating a wrapper around the content you want floated, you can then use the ::after or ::before pseudo selectors to vertically align your content within the wrapper. You can adjust the size of that content all you want without it affecting the alignment. The only catch is that the wrapper must fill 100% height of its container.

http://jsfiddle.net/jmdrury/J53SJ/

HTML

<div class="container">
<span class="floater">
<span class="centered">floated</span>
</span>
<h1>some text</h1>
</div>

CSS

div {
border:1px solid red;
height:100px;
width:100%;
vertical-align:middle;
display:inline-block;
box-sizing: border-box;
}
.floater {
float:right;
display:inline-block;
height:100%;
box-sizing: border-box;
}
.centered {
border:1px solid blue;
height: 30px;
vertical-align:middle;
display:inline-block;
box-sizing: border-box;
}
h1 {
margin:0;
vertical-align:middle;
display:inline-block;
box-sizing: border-box;
}
.container:after, .floater:after, .centered:after, h1:after {
height:100%;
content:'';
font-size:0;
vertical-align:middle;
display:inline-block;
box-sizing: border-box;
}

A possible solution is to make wrapper div flex with items aligned on center as specified by https://spin.atomicobject.com/2016/06/18/vertically-center-floated-elements-flexbox/.

I do my best to avoid using floats... but - when needed, I vertically align to the middle using the following lines:

position: relative;
top: 50%;
transform: translateY(-50%);