One way for a military leader to end up in that situation would be to be in a society with a long and august tradition of honor and fair play and chivalry who wins with tactics like the Trojan horse and trickery that win battles in dishonorable ways according to the old school of thinking.
To capture the sense of it, imagine how many people might despise a Presidential candidate who wins primary after primary by the dozen en route to a nomination for his party, but does so by resorting to demagoguery, low blows, incivility, appeals to people's basest instincts, mockery of honorable men, and outright blatant lies. Even if someone like that won the "war" by being elected President, lots of people might despise him and think poorly of him.
There are fairly direct military analogies to that kind of political journey that could lead to the same kind of perception.
For example, suppose that the military leader in question won a key battle by raising a white flag of surrender and then attacking the soldiers who had come to accept their surrender with hidden weapons and soldiers who ambushed their leaders. It would be a win, but a dirty one.
Perhaps another battle is won by capturing an opposing leader's family and publicly torturing them until the opposing leader gives in, and then slaughtering the tortured family members once he had the opposing leader's surrender in hand.
Maybe another battle is won by poisoning the lake that is the sole water supply for the region, killing huge numbers of civilians and rendering the entire area uninhabitable for another decade or more.
Maybe his troops are relatively unskilled and undisciplined, prone to raping and pillaging without authorization to do so, prone to infighting among themselves often resorting in pointless, deadly duels between members of his own force, and he himself is fat, lazy, rude, capricious with his treatment of his underlings, not very competent in one on one combat, and prone to make serious gaffs that show a lack of knowledge of the places that he is conquering.
It is easy to see how such a man could have several big military successes and yet still be viewed as mediocre.