I use 640x480 on my 27" JVC. The TV's service menu along with Powerstrip helps to constrict the screen just enough to fit it perfectly.
I'm not sure I would've been able to get 800x600 on there. The only purpose to do such a thing would be if you plan on using Windows at various times, or for premade layouts for frontends. Otherwise, is there any reason to use 800x600?
I have an ATI as well. Something in the low 9000s I believe.