Actually...
Here is the critera i need: a Truely wickedly evil protaginist, a Damsel in distress captured and sevearly threattened by said protaginist, and a hero who against Incredible odds rescues her.
if you really meant "Truely wickedly evil protaginist", I think Ikari Gendo (Shinji's father) from Evangelion fits perfectly (at least if you think of him as a protagonist). The "damsel in distress" would take a little work (either putting Rei in destress caused by Gendo - which wouldn't be that far off, or working with Asuka when she's trapped or overwhelmed), but the "against incredible odds rescues her" woud be pretty easy.
Then again, there really
are a lot of EVA videos already, so whether it would make sense or not might be aside the point.
Other possible "evil protagonists" might include the head of the family in "Fruits Basket" - but good luck with the damsel (Honda-san freaks out a lot, but I don't know as that counts as distress) and incredible odds. FLCL has a somewhat evil protagonist (Haruko), a distressed female (Mamimi at a few points), and a hero boy/robot fighting against incredible odds, but the danger doesn't come from Haruko, it just comes with her.
My best suggestion would be Princess Tutu. It's obscure, but has every one of the elements you mentioned, through multiple possible combinations of chracters and story sections. Being based on woven-together fairy tales and ballet plots it's full of good/evil/distressed damsels (male and female)/brave knights/incredible odds/general fantasy look... and has an evil character who you just have to love and sympathize with in the anime, a seemingly evil character who turns out to be a protagonist, and a hero prince who is twisted by a spell into an evil one for some time leading up to the end of the story. It's been licenced (about a week ago), but there are currently no plans to actually release the DVDs in America (the licence was bought for the manga), so you can only get it as digisubs (which you can get good quality out of if you know what you're doing with the editing/encoding process) right now, but the plot is too perfect for what you're asking for to overlook.
Just get beyond the first few episodes before deciding what you think of it, as it changes dramatically just before the half-way point.
I have all the episodes of this anime that can be used as source material.
How could i forget about scrapped princess.... that is a good one, I second that ;p Although it is set in the future, not the past, but could work sicne the world is actually medieval based. Its something like matrix, where they are in an artificial world created for them by the aliens, wich happens to be set to the medeival period. THere is an antagonist, but to get good scenes between the 2 of them, there would be some futuristic elements in it, like the mechas and some of the technology in it. But it could possibly work.
[/size]