Regina’s redeemed, yes, but again, not by virtue of a man, but by virtue of her own work.
I was thinking of Snow as the redeemed villain, from when she gave up part of her memory and set out on that path of vengeance against Regina.
AKA’s example of Will and Anastasia does work though.
I think the femme fatale description might be due to how characters behave when we’re first introduced to them. Ana was optimistic and cheerful when she was young, and Regina was kind and selfless, but we don’t think of them as fundamentally that way because we didn’t learn about that earlier part of their lives until later. Snow was cruel and motivated by wrath for a while, but we got to see an earlier good phase of her life before we saw the bad phase.