[setishock]

Try this:

<!-- logo -->
<a name="top"></a>
<center>
<table border="0" width="100%" cellpadding="0" cellspacing="0" align="center" style="background-image:url($stylevar[imgdir_misc]/headbg.gif)">
<tr>

<td align="left" valign="top"><a href="$vboptions[forumhome].php$session[sessionurl_q]"><img src="$stylevar[imgdir_misc]/head_left.gif"  border="0" alt=""/></a></td>
<td align="right" valign="bottom"><img src="$stylevar[imgdir_misc]/head_right.gif" alt="" /></td>
</tr>
</table>
</center>

<!-- /logo -->
<!-- content table -->
$spacer_open

$_phpinclude_output

You have to split your header into three sections.
head_left.gif - the left most portion of your header
head_right.gif - the right most portion of your header
headbg.gif - a one or two pixel "filler" that will keep the header looking full no matter what the width. It should be solid for best effect.
Upload the three files to your /images/misc folder for the theme and you're ready!

That replaces the header code.

I didn't write that. Some one gave it to me. It really works. Make the left and right panels a size so when it's viewed at a real low resolution they come together. When viewed at higher resolutions the filler does just that. It fills in.
Get creative with a gradient or a pattern.