Weird...I have three options: Normal, Stretch and Fill on my Westinghouse 42" HDTV...normal is the 4:3 as you see, the Stretch makes it fill the whole 16x9 space while keeping the height the same, and the fill essentially zooms into the center of the picture until there is enough horizontal imagery to fill the screen, cutting off the top and bottom of the image.
It also worked the same way with the digital converter box I used about 5 years ago with my standard def TV. 😕
I agree, it should work...like you say.