La pregunta sobre cómo centrar el div se refiere al <div class="tabla_centrada1">.
Como el class="centrado1" tiene un margin distinto a auto, ya no hay forma de que se centre. Mi solución apuntaba a seguir dejando el <div class="centrado1"> con margin:0 auto; y hacer una chapucilla que equivalga a ese margin mediante un nuevo div que tenga height:50px. Es simplemente una sugerencia. No me gusta nada esta solución, pero es que no se me ocurre otra si no quiero volver al <center>:
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" lang="es-es">
<HEAD>
<TITLE>New Document</TITLE>
<style type="text/css">
.separador_para_suplir_el_margin { margin-top:50px;}
.centrado {margin:0 auto; width:300px; height:200px; background:#DEDEDE;}
.tabla_centrada {margin:0 auto; padding:10px;}
</style>
</HEAD>
<BODY>
<div class="separador_para_suplir_el_margin"><div>
<div class="centrado">
Este div se centra, por tener margin:auto
<table class="tabla_centrada"><tr><td bgcolor="FF0000">Tabla que debe estar centrada</td></tr></table>
</div>
</BODY>
</HTML>