By the time you kill the medic, the heavy has almost killed you so you can make a dent in the heavy just in time to die and have the medic come back and heal him while you're waiting to respawn! FUN!!!
Err... you don't just stand there and soak up bullets. Heavies (and thus the medic) are very slow targets. As a soldier, you can very easily pop around corners and take out the medic without exposing yourself for long. As a scout, it's very common to jump in, take out the medic, and run out. In addition, without uber, the heavy-medic combo is useless against turrets, snipers, spies, what-have-you.
If the heavy and medic combo is dominating your team, either the combo is doing something very, very right or your team is doing something very, very wrong. Individual skill matters.
And oh, you're talking about how their team apparently has at least two medics and one heavy, while your team apparently doesn't have any medics. Maybe that's the problem?