Hola 
tistklehoff 
Puedes intentar con esto. 
Tabla siempre centrada, sin tamaño definido:  
 Código HTML:
 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>Tabla sin tamaño definido siempre centrada</title>
<style type="text/css">
* {
	outline: 0;
    font-family: Verdana, Arial, Tahoma, Helvetica, sans-serif;
    font-size: 10px;
    color: #000;
	text-decoration: none;
}
.tabla {
	border-collapse: collapse;
	border: 1px solid #A6B0F8;
	margin: 0 auto;
}
.celda {
	border: 1px solid #A6B0F8;
}
div.paginacion {
	padding: 0;
	background-color: #A6FFE2;
	height: 30px;
	line-height: 30px;
}
div.paginacion ul.menu_paginacion {
	font-size: 10px;
}
div.paginacion ul.menu_paginacion li {
	float: left; 
	list-style-type: none;
	padding: 0 10px;
}
div.paginacion ul.menu_paginacion li.actual {
	color: red;
	font-weight: bolder;
	font-size: 12px;				
}
div.paginacion ul.menu_paginacion li a {
	text-decoration: none;
	color: #000;
	font-weight: bold;
}
.centrado {
	text-align: center
}
</style>
</head>
<body>
<p class="centrado">Tabla sin tamaño definido siempre centrada (tamaño que se adapta a su contenido).</p>
<p class="centrado">Testado en iexplorer 7, firefox 3.5, opera 9 y safari 4</p>
<table class="tabla">
	<tr>
		<td class="celda">Datos datos</td>
		<td class="celda">Datos datos</td>
		<td class="celda">Datos datos</td>
		<td class="celda">Datos datos</td>
		<td class="celda">Datos datos</td>
	</tr>
	<tr>
		<td class="celda"> </td>
		<td class="celda"> </td>
		<td class="celda"> </td>
		<td class="celda"> </td>
		<td class="celda">Datos datos datos</td>
	</tr>
	<tr>
		<td class="celda"> </td>
		<td class="celda"> </td>
		<td class="celda"> </td>
		<td class="celda"> </td>
		<td class="celda"> </td>
	</tr>
	<tr>
		<td class="celda"> </td>
		<td class="celda">Datos datos datos datos</td>
		<td class="celda"> </td>
		<td class="celda"> </td>
		<td class="celda"> </td>
	</tr>
	<tr>
		<td class="celda"> </td>
		<td class="celda"> </td>
		<td class="celda"> </td>
		<td class="celda"> </td>
		<td class="celda"> </td>
	</tr>
</table>
		<div id="paginacion" class="paginacion">
			<ul class="menu_paginacion">
				<li class="actual"><a href=""><<</a></li>
				<li class="actual"><a href=""><</a></li>				
				<li class="actual">1</li>
				<li class="actual"><a href="">2</a></li>
				<li class="actual"><a href="">3</a></li>
				<li class="actual"><a href="">></a></li>
				<li class="actual"><a href="">>></a></li>					
			</ul>
		</div>
</body>
</html>  Esto es un prototipo genérico, con parte de tu estilo, pero que debes adaptar a tu diseño. Comenta algo. 
Bye