Yes, it does indeed seem like the extra space should be there--I imagine the real question is why it isn't there in some cases. I suppose it's more of an academic question than anything.
But tell me if the following doesn't strike you as slightly odd:
<table width="200" cellpadding="0" border="1" bgcolor="#cccccc">
<tr><td><div><p>test</p></div></td></tr>
</table>
<table width="200" cellpadding="0" border="1" bgcolor="#cccccc">
<tr><td><div style="border: 1px solid;"><p>test</p></div></td></tr>
</table>
<table width="200" cellpadding="0" border="1" bgcolor="#cccccc">
<tr><td><div style="border: 1px solid;"><p style="margin: 0;">test</p><div></td></tr>
</table>
[php]<table width="200" cellpadding="0" border="1" bgcolor="#cccccc">
<tr><td><div><p>test</p></div></td></tr>
</table>
<table width="200" cellpadding="0" border="1" bgcolor="#cccccc">
<tr><td><div style="border: 1px solid;"><p>test</p></div></td></tr>
</table>
<table width="200" cellpadding="0" border="1" bgcolor="#cccccc">
<tr><td><div style="border: 1px solid;"><p style="margin: 0;">test</p><div></td></tr>
</table>[/php]
Not likely a realistic situation; it just seems to me as a bit curious.
Oh--and I wouldn't want the web gurus around here to think I didn't know how to use the id parameter--don't worry; it wasn't intended for public consumption!
<span style="color: red;">Edit: I see IE is playing different tricks on me now. There's only extra space at the bottom, and even without the border. Okay. Perhaps this one should be chalked up to browser misimplementation?</span>