I have reworked my sample template so you can see all three of your requested formats in action.
This is a CSS solution, no tables involved. I have set this up so the side columns are fixed width the header/footer are fixed height. Everything else is fluid.
With all modern browsers, excepting for IE7, the content is centered both vertically and horizontally. IE7 has issues with its box model. I believe IE8 have these resolved.
The center box does center vertically in IE7 because I nested a 1 cell table in the center div as a hack around IE7 box model problems. I know this is dumb and ugly but it was just to show it worked.
See it in action - Three Column Full Screen Layout
I am a bit surprised this answer did not garner a single vote or capture the bounty. It works, its simple, and it fulfills everything the OP asked for. Oh well.
The CSS
DIV { text-align: center }
#h0, #f0 { float: left; clear: both }
#h1, #f1 { height: 100px; float: none; width: 800px }
#l0 { float: left; clear: left; }
#c0, #r0 { float: left; clear: none }
#l1, #r1 { width: 150px }
#c1 { width: 500px }
#l1, #r1, #c1 { height: 350px }
#h0, #f0 { background-color: orange }
#l0 { background-color: red }
#r0 { background-color: blue }
#c0 { background-color: yellow }
#h1, #f1, #l1, #r1, #c1
{ display: table-cell; vertical-align: middle; }
The HTML
<div id="h0"><div id="h1">
header
</div></div>
<div id="l0"><div id="l1">
left column
</div></div>
<div id="c0"><div id="c1">
<img alt="dilbert (3K)" src="../gif/dilbert.gif" height="82" width="80" />
</div></div>
<div id="r0"><div id="r1">
right column
</div></div>
<div id="f0"><div id="f1">
footer
</div></div>