Bastante simple era, pero como siempre hay que dar con la tecla. Aca el codigo que me funciono en Internet Explorer y en Firefox. Aca el codigo para los apurados.

var width = document.documentElement.clientWidth;
var height = document.documentElement.clientHeight;
var top = (height  - divHeight) / 2 document.body.scrollLeft;
var left = (width  - divWidth) / 2 document.body.scrollTop;
myDiv.style.left = left "px";
myDiv.style.top = top "px";

Analicemos lo puesto arriba, primero voy a tomar el ancho y alto de la ventana del browser

var width = document.documentElement.clientWidth;
var height = document.documentElement.clientHeight;

Luego, voy a usar un algoritmo muy simple para centrar teniendo en cuenta lo que ha hecho scroll horizontal y verticalmente la ventana.

var top = (height - divHeight) / 2 document.body.scrollLeft;
var left = (width - divWidth) / 2 document.body.scrollTop;

Por ultimo posicionamos nuestro DIV de esta manera:

myDiv.style.left = left "px";
myDiv.style.top = top "px";

Voila!