Yoooo,

After messing with the setup on Quake III fullscreen mode, it turns out that even though you configure screen modes in the monitor preferences, Quake III was still not doing things correctly in full screen mode. It would be shifted on the upper-left corner.

Turns out that you must set the Color Depth manually to 32bit (I didn't try 16bit), and then Quake III happily was in full screen mode without black borders and centered correctly.

Hope this helps someone out there!