But Dex is the 'good guy', working under Harry's Code. Evil turned to a more worthy purpose (for a given value of 'more worthy').
The function of the Code is to keep Dexter from getting caught (and pretty transparently, to allow the audience to like him - but that's the writers' manipulation and Dex doesn't know anything about that

). He's still essentially a guy who kills because he likes to kill, no more savory the OP's Romulan who blows up planets because he likes to blow up planets.
So Dexter is an example of how to take a no-excuses "evil" character and make him sympathetic enough that the audience will root for him. Tough to do but not impossible.
Which is why I said 'good guy'
It's a dodgy area to get into. Dex sees the people he kills as beneath him, and he would not (intentionally) harm anyone outside the Code, even respects them to a point.
Circling back to my earlier point about a villian winning all the way to the end. What would it look like? Imagine the Master from Doctor Who taking over a space empire far fromthe Doctor's reach. Or Gollum capturing the Ring and Sauron gaining victory over the Fellowship and Middle Earth.
What would happen next?
This is the crux of the matter as to whether the villain is well created or not. Does he then just destroy what he has taken because that is all he can do, or does he in effect become the good guy, by providing stable government, justice, and in effect care for his peasants? What the hell is the point of destroying something it has taken years to acquire?
A really interesting example of this is Lord Havelock Vetinari, Tyrant of Ankh-Morpork. In Ankh-Morpork, it's one man, one vote - Vetinari is the man, he has the vote. He has spies, he manipulates people, he is against unnecessary cruelty but is right alongside the idea on necessary cruelty... and the city works. And because the city now works so very well, no one wants to get rid of him. He is too good to replace!
He isn't a character I'd want to cross: two great moments from him.
In the books, he often says to people petitioning him, by way of dismissal, "Don't let me detain you."
And in the TV version of 'The Colour of Magic', as played by Jeremy Irons, he says to the main character, "What
are we going to do with you, you little
scamp?' It's all in the delivery, it cracks me up a lot every time.
ETA: found a clip!
http://www.youtube.com/watch?v=BwOowHV88wQ
Actually, now I think about it, that would be my suggestion to the OP and
Mr Laser Beam - read the relevant Discworld books where Vetinari has a role, and you see a villain who has gone so far... he's become the good guy. And he really is.
