The Germans dont "always' win, but they do tend to take a greater slice of the victory pie (60% wins wouldnt be an unreasonable estimate). There are probably lots of factors in this (my pet theory goes that people with far-right ideologies have no friends, and therefore have countless hours to hone their craft, and when they play this game, their team of choice is a no brainer), but TW does make efforts to curb the advantage, say by throwing a trench here, a tank there, et cetera. The German to Soviet win ratio was actually much worse when the game first came out. Now I like to think of playing Soviet as being more of a challenge, but a reasonable one. It also really depends on the map. The Soviets generally (with some really painful exceptions) dont have too much of a problem winning apartments, but a Red October Factory victory is a rare treat for the Soviets.
To make the whole axis and allies thing fair, we should have a map that throws an Italian force into the frey, and then the Soviets will take the 60% victory slice.