Despite the poor CSS support in various email clients, people have come up with some pretty nice designs that are well tested, so perhaps check those out. E.g.:
Some of those layouts use pretty fancy stuff, so I assume they are designed with progressive enhancement in mind (or graceful degradation, as the case may be). Have a look at how they handle background images.
<td style="background-image: url(images/left-side.jpg); background-repeat: repeat;" background="images/left-side.jpg" bgcolor="#d4d1cd" valign="top" width="22"></td>