I'd set "enforce aspect ratio" checked, "clean stretch" to auto, "stretch using hardware" checked, aspect ration to 4:3, and the resolution size to whatever you know works. The most important is "enforce aspect ratio".
FWIW, you tried setting the "clean stretch" to horizontal or vertical. What that means it makes sure it's stretched by a integer in that dimension to fit on the screen, not that it only stretches that.