I thought I had everything sorted when it comes to Outlook 2007 and 2010, but I forgot the fact that it can be so weird about borders.
The two things I learned today are:
1. Always remember to use border-collapse: collapse on your tables in Outlook, and
2. When Outlook is displaying a 2px border when you asked for a 0px border, remember that (weirdly) shorthand works better for borders in ALL email clients.
This page really helped me out — turns out that, unlike any other attributes, borders benefit from being written in shorthand, i.e:
border-top: 1px solid #000000;
So there you go. That eliminated all of my woes in Outlook, where I was trying to specify a border-bottom-width of 0px.