First of all, please note that the cellpadding and cellspacing attributes are not deprecated in HTML 4 (and not even in XHTML 1.1). I believe this was due to CSS1 not having a replacement for them at the time HTML 4 was written.
However then CSS2 came along, with its lovely properties to control table borders. Only problem is, most of them aren't supported in IE6 on Windows.
The only one that is is border-collapse, in IE5+. So simply set this to collapse, like so:
border-collapse: collapse;
If you want to remove all cell padding from all tables on a page, do this:
table {
border-collapse: collapse;
}