Well, I'm reasonably sure this is because of the difference between "real" black, which is RGB(0,0,0) and "video" black -- which has a luminance of 16. When converted correctly between RGB<->YUV, one will be correctly converted to the other and this problem won't occur.
It is my guess that the empty timeline space is RGB(16,16,16) which, when converted to YUV has a luminance of 32… thus your washed-out black.
I am not exactly sure, but I think this is some kind of "holdover" from the old days of Premiere where everything was processed exclusively as RGB, and they set the background black to be within legal range – but then they started performing the conversions more correctly which, in this case, begat a new problem. I cannot substantiate this. It is only a guess as to the nature of the problem.
To make a long story short, I essentially do what you do and create my own black background. I am so paranoid that I actually make a black Photoshop file [RGB(0,0,0)] and use that to fade in/out from -- just to make sure it is as black as black can be. I have a long and complicated history with Premiere's goofy colorspace conversions and, although many of these have now been rectified, I rely on old habits.
At the very least I'm glad to know I'm not the only one neurotic about these things. Those little tiny flickers in between clips drive me crazy.
The bad news is I was hoping there was a simple setting somewhere I was forgetting.