You are fixated on whether the people in question are evil and not whether they do evil. By the rules, you cannot have evil paladins. We all know this. But you can have paladins that do evil without falling and still remain good. This does not retroactively make their actions non-evil, nor does it mean they should Fall for their ignorance. It means good people (paladins included) can do evil and still be good.
Why does it matter if the other party has an incomplete picture of the situation? Does being punched hurt less if the person who punched you did it by accident? Does it cause less harm?
A villain who does evil is still a villain even if they are good-aligned. Being a genuinely good person does not erase the damage you cause.
Also, the cosmos does not judge whether you are a villain or not. That is not a thing that exists. In-universe, people judge you a villain based on the evil you do, and out of universe, the author and the audience do the same.
There is no such thing as "well, you may think this poor ignorant paladin a villain for defending the corrupt evil king, but as you can see here, the cosmos has signed a decree declaring him not-a-villain, sorry!"
Edit:
Clerics and druids lack the "unwitting" part and also make use of the atonement spell, so we cannot say that part is meant for paladins.