Simple. IE6 and above will happily center your table with "margin: 0 auto;" if only the page renders in "standards" mode. To make this happen you need a valid doctype declaration, such as
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
or
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
True, IE5.5 and below will still refuse to center the table but perhaps you can live with that, especially if the page is still functional with the table left aligned. I think by now users of IE5.5 and below are fairly used to some odd looking websites - but you still need to ensure that those visual glitches don't render your site unusable.
Happy coding!
EDIT: Sorry, I should perhaps point out that you do not have to have a "strict" doctype to get IE6 and up into "standards" rendering mode. I realised it might seem that way from the doctype examples I posted above. For example, this doctype declaration will of course work equally:
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">