It sounds to me like the DVD's are actually full screen presentations. By setting the DVD players to 4:3 your TV is going to stretch the picture to fill the screen as it's own setting. However, when you had the setting to 16:9 it sent out the 4:3 picture with black bar data on the sides. This is if you have widescreen TV's by the way.
Anyway, on the back of the DVD it will tell you the presentation aspect ratio of the movie. Just FYI.
Forgive me if this is something you know already.