The only (and the best cross-browser) way as I know is to use an inline-block helper with height: 100% and vertical-align: middle on both elements.

So there is a solution: http://jsfiddle.net/kizu/4RPFa/4570/

.frame {
    height: 25px;      /* Equals maximum image height */
    width: 160px;
    border: 1px solid red;
    white-space: nowrap; /* This is required unless you put the helper span closely near the img */

    text-align: center;
    margin: 1em 0;
}

.helper {
    display: inline-block;
    height: 100%;
    vertical-align: middle;
}

img {
    background: #3A6F9A;
    vertical-align: middle;
    max-height: 25px;
    max-width: 160px;
}

<div class="frame">
    <span class="helper"></span><img src="http://jsfiddle.net/img/logo.png" height=250px />
</div>
<div class="frame">
    <span class="helper"></span><img src="http://jsfiddle.net/img/logo.png" height=25px />
</div>
<div class="frame">
    <span class="helper"></span><img src="http://jsfiddle.net/img/logo.png" height=23px />
</div>
<div class="frame">
    <span class="helper"></span><img src="http://jsfiddle.net/img/logo.png" height=21px />
</div>
<div class="frame">
    <span class="helper"></span><img src="http://jsfiddle.net/img/logo.png" height=19px />
</div>
<div class="frame">
    <span class="helper"></span>
    <img src="http://jsfiddle.net/img/logo.png" height=17px />
</div>
<div class="frame">
    <span class="helper"></span>
    <img src="http://jsfiddle.net/img/logo.png" height=15px />
</div>
<div class="frame">
    <span class="helper"></span>
    <img src="http://jsfiddle.net/img/logo.png" height=13px />
</div>
<div class="frame">
    <span class="helper"></span>
    <img src="http://jsfiddle.net/img/logo.png" height=11px />
</div>
<div class="frame">
    <span class="helper"></span>
    <img src="http://jsfiddle.net/img/logo.png" height=9px />
</div>
<div class="frame">
    <span class="helper"></span>
    <img src="http://jsfiddle.net/img/logo.png" height=7px />
</div>
<div class="frame">
    <span class="helper"></span>
    <img src="http://jsfiddle.net/img/logo.png" height=5px />
</div>
<div class="frame">
    <span class="helper"></span>
    <img src="http://jsfiddle.net/img/logo.png" height=3px />
</div>

Or, if you don't want to have an extra element in modern browsers and don't mind using Internet Explorer expressions, you can use a pseudo-element and add it to Internet Explorer using a convenient Expression, that runs only once per element, so there won't be any performance issues:

The solution with :before and expression() for Internet Explorer: http://jsfiddle.net/kizu/4RPFa/4571/

.frame {
    height: 25px;      /* Equals maximum image height */
    width: 160px;
    border: 1px solid red;
    white-space: nowrap;

    text-align: center;
    margin: 1em 0;
}

.frame:before,
.frame_before {
    content: "";
    display: inline-block;
    height: 100%;
    vertical-align: middle;
}

img {
    background: #3A6F9A;
    vertical-align: middle;
    max-height: 25px;
    max-width: 160px;
}

/* Move this to conditional comments */
.frame {
    list-style:none;
    behavior: expression(
        function(t){
            t.insertAdjacentHTML('afterBegin','<span class="frame_before"></span>');
            t.runtimeStyle.behavior = 'none';
        }(this)
    );
}

<div class="frame"><img src="http://jsfiddle.net/img/logo.png" height=250px /></div>
<div class="frame"><img src="http://jsfiddle.net/img/logo.png" height=25px /></div>
<div class="frame"><img src="http://jsfiddle.net/img/logo.png" height=23px /></div>
<div class="frame"><img src="http://jsfiddle.net/img/logo.png" height=21px /></div>
<div class="frame"><img src="http://jsfiddle.net/img/logo.png" height=19px /></div>
<div class="frame"><img src="http://jsfiddle.net/img/logo.png" height=17px /></div>
<div class="frame"><img src="http://jsfiddle.net/img/logo.png" height=15px /></div>
<div class="frame"><img src="http://jsfiddle.net/img/logo.png" height=13px /></div>
<div class="frame"><img src="http://jsfiddle.net/img/logo.png" height=11px /></div>
<div class="frame"><img src="http://jsfiddle.net/img/logo.png" height=9px /></div>
<div class="frame"><img src="http://jsfiddle.net/img/logo.png" height=7px /></div>
<div class="frame"><img src="http://jsfiddle.net/img/logo.png" height=5px /></div>
<div class="frame"><img src="http://jsfiddle.net/img/logo.png" height=3px /></div>

How it works:

  1. When you have two inline-block elements near each other, you can align each to other's side, so with vertical-align: middle you'll get something like this:

Two aligned blocks

  1. When you have a block with fixed height (in px, em or another absolute unit), you can set the height of inner blocks in %.

  2. So, adding one inline-block with height: 100% in a block with fixed height would align another inline-block element in it (<img/> in your case) vertically near it.