I haven't read this whole thread, but here are some resolutions I've come up with that might be useful to someone.
All of these are for Radeon cards (Radeon 9500 specifically, but I don't think it should matter what exact model you have). I got all these running with a DVI connection to my Hitachi SWX 57 inch TV. The overscan adjusted resolutions are the least amount of overscan I could get on the SWX, while still having no underscan whatsoever.
480p, 4:3 mode
overscan adjusted (Hitachi SWX 57)
480p, widescreen mode
540p, widescreen mode
720p, widescreen mode