[Edit for typo]
algi: Now, this is all speculation and to be taken with a grain of salt, because I haven't met Viconia, yet in this playthrough, and didn't get the opportunity to discover. And my experience tells me that even slight changes in the wording of dialogues can have huge impact on important decisions.
1. We know in fact she is evil after a detect evil.
Her game alignment is evil, not her. She talks tough, but she's not inherently evil, such as a demon would be. Her alignment can even be switched in ToB with the right guidance.
2. It's the decision of Baldur's Gate to uphold the law by hiring mercenaries. Whether people have democratic rights (for due process) or not is besides the point for the paladin. (This is explicitely stated in the CPH. Tyranny is acceptable for the paladin. And even if she witnesses unacceptable horrible practices, like slavery, it's not her duty to free every slave in the country. But, of course, this is a perfect opportunity to save one person from excessive injustice, if it's actually true.)
So if a paladin resides in the dominion of an evil tyrant, who enacts and enforces evil laws and actions, the paladin is upholding evil by default. This is what I was saying about allowing an ethos to have priority over good judgement. By extension, such a paladin would be fallen; would be evil.
3. It doesn't matter if the mercenary is racist or not, if he's doing his job properly. Don't forget that a Flaming Fist mercenary is the authority in these parts. Now, he might act against his order, but we don't know that.
Just as you don't know whether the mercenary is "doing his job properly". Just as you don't know that Viconia is evil (besides her alignment) when you meet her, nor whether she has committed any crime whatsoever. Blindly upholding a law just because it's a law is madness.
4. It is possible that in this case Viconia is a victim of injustice, and while she's evil,
No she isn't. Her alignment is.
she didn't in fact do anything bad, but as we know she's evil,
No she isn't. Her alignment is.
she has to be really convincing to persuade a paladin that this is indeed extreme injustice that must be stopped, even going against the law of Baldur's Gate.
No, she needs to be not of evil alignment, otherwise the paladin just won't listen.
Don't forget that a paladin is euqally a servant to law as being good.
So what law will you see Viconia break to deserve death? What proof can the Flaming Fist offer? None on both counts.
And this might even be a very hard and interesting dilemma WHEN I get to that point. But as I said, I haven't, so I'll see what decision I will make eventually when I get there.
We will see.