Googlefrog, the winrate of rushed Paladin feels quite high to me. Paladin is counterable if the team works together but all too often its a rushed Paladin smashing down whatever is in its lane while the rest of the team does whatever in their own individual actions.
In a sense a Paladin represents the metal investment of a team working together against the metal investment of another team not working together.
I remember that a team with 2-3 facs spamming nothing but Dirtbags managed to consistently sandbag a Paladin rush until it was killed. The team must work together.
In that sense a rushed Paladin is a game defining weapon.