The only way this is possible is if you're not getting a clean key on your chromakey shot. Toggle the visibility of the track that contains the chromakey shot on and off; does the brightness of the background change? If so, it's your keyed shot.
Most chromakey effects have a preview mode in which you can see a grayscale representation of your alpha channel; that's what you're generating when you do a key. If your subject is not a solid white and the area surrounding your subject a solid black (commondly called a high-contrast or "hi-con" matte), but is instead a mish-mash of gray, those pixels are not being optically removed and are being composited with the background.
Using the alpha preview mode of your effect, you can tweak the effect parameters to push the black pixels closer to black and the white pixels closer to white. You can also use the Y/C waveform monitor in the Program Monitor in this mode to make sure the luminance levels are at extremes. How black should it be? In the words of Nigel Tufnel, "It's like, how much more black could this be? And the answer is none. None more black."
Hope that helps...
If I "over expose" the blue screen, the background ends up correctly exposed behind the subject.
What Colin said.
You simply are not pulling the key correctly no matter what the BG is.
Can you post up a frame of scenes with "over and under" BGS (not keyed so we can test a key)