I'm not quite sure why that is happening. What layout are you trying to achieve, does it really need to be a table? You shouldn't layout pages with tables, they should only be used for true tabular data.
Have you considered using divs?
Throw it through a validator and I'm sure you'll get a little closer.
Actually - what you're seeing is normal behavour for IE: add border="1" to your main table and it'll show you what's happening a little clearer.
The right answer would be: don't layout your page using tables.
The technical answer would be: your table cells are doing what they are supposed to do, i.e. you can't solve your problem with the code structure you use.
The hacky answer would be: having the cells on the left and right to be exactly 37px high, you'll have to add 2 additional nested tables in the left and right cell.
What if you try it like this:
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head></head>
<body bgcolor="#AA5566" >
<table width="100%" border='1'>
<tr>
<td valign="top">
<table bgcolor="#112233" height="37" width='100%'><tr><td>asdf</td></tr></table><br />
Other content
</td>
<td width="600" rowspan="2" >
<table width="600" height="800"><tr><td>asdf</td></tr></table>
</td>
<td valign="top">
<table bgcolor="#112233" height="37" width='100%'><tr><td>asdf</td></tr></table><br />
Other content
</td>
</tr>
</table>
</body>