Edit: Previous table-based image positioning had issues in Internet Explorer 11 (max-height doesn't work in display:table elements). I've replaced it with inline based positioning which not only works fine in both Internet Explorer 7 and Internet Explorer 11, but it also requires less code.
Here is my take on the subject. It'll only work if the container has a specified size (max-width and max-height don't seem to get along with containers that don't have concrete size), but I wrote the CSS content in a way that allows it to be reused (add picture-frame class and px125 size class to your existing container).
In CSS:
.picture-frame
{
    vertical-align: top;
    display: inline-block;
    text-align: center;
}
.picture-frame.px125
{
    width: 125px;
    height: 125px;
    line-height: 125px;
}
.picture-frame img
{
    margin-top: -4px; /* Inline images have a slight offset for some reason when positioned using vertical-align */
    max-width: 100%;
    max-height: 100%;
    display: inline-block;
    vertical-align: middle;
    border: 0; /* Remove border on images enclosed in anchors in Internet Explorer */
}
And in HTML:
<a href="#" class="picture-frame px125">
    <img src="http://i.imgur.com/lesa2wS.png"/>
</a>
 DEMO 
/* Main style */
.picture-frame
{
    vertical-align: top;
    display: inline-block;
    text-align: center;
}
.picture-frame.px32
{
    width: 32px;
    height: 32px;
    line-height: 32px;
}
.picture-frame.px125
{
    width: 125px;
    height: 125px;
    line-height: 125px;
}
.picture-frame img
{
    margin-top: -4px; /* Inline images have a slight offset for some reason when positioned using vertical-align */
    max-width: 100%;
    max-height: 100%;
    display: inline-block;
    vertical-align: middle;
    border: 0; /* Remove border on images enclosed in anchors in Internet Explorer */
}
/* Extras */
.picture-frame
{
    padding: 5px;
}
.frame
{
    border:1px solid black;
}
<p>32px</p>
<a href="#" class="picture-frame px32 frame">
    <img src="http://i.imgur.com/lesa2wS.png"/>
</a>
<a href="#" class="picture-frame px32 frame">
    <img src="http://i.imgur.com/kFMJxdZ.png"/>
</a>
<a href="#" class="picture-frame px32 frame">
    <img src="http://i.imgur.com/BDabZj0.png"/>
</a>
<p>125px</p>
<a href="#" class="picture-frame px125 frame">
    <img src="http://i.imgur.com/lesa2wS.png"/>
</a>
<a href="#" class="picture-frame px125 frame">
    <img src="http://i.imgur.com/kFMJxdZ.png"/>
</a>
<a href="#" class="picture-frame px125 frame">
    <img src="http://i.imgur.com/BDabZj0.png"/>
</a>
 
 
Edit: Possible further improvement using JavaScript (upscaling images):
function fixImage(img)
{
    var $this = $(img);
    var parent = $this.closest('.picture-frame');
    if ($this.width() == parent.width() || $this.height() == parent.height())
        return;
    if ($this.width() > $this.height())
        $this.css('width', parent.width() + 'px');
    else
        $this.css('height', parent.height() + 'px');
}
$('.picture-frame img:visible').each(function
{
    if (this.complete)
        fixImage(this);
    else
        this.onload = function(){ fixImage(this) };
});