Shoul I stretch the file, if it's original shape is 16:9, to 4:3 when encoding? I plan on doing this and afterwards when using dvdmaestro set the movie as widescreen (16:9), whereas dvdmaestro squeezes the picture together.
Does this make me gain any quality at all instead of encoding it with black borders from the beginning?

Generally it does not because encoding in 4:3, so without the borders, ask for more bytes . And as the place on the disc is still the same you have to reduce the whole quality of the encoding to fit the movie on the DVD.

Now, if you are doing a DVD with only one movie, let say that you will encode it with the border at Q=10. Without the border the quality will be Q=15. (I assuem here you are using CCE). There is no real diff between 10 and 15 and THEN the gain you will have by using the anamorphic mode of your TV will be interresting.

NOTE: you plan to see that on a widescreen TV, do you ? Else there is NO GAIN in this operation !

PS: I'm currently doing Titanic, that is 3h long and I do a 16:9 -> 4:3 conversion

Yeah I plan on seeing it on a widescreen tv, but I think I'll stick to encoding with borders, keeping in mind that many of my friends don't have a widescreen tv