That got me thinking about the very concept of an enemy, what it meant to be one, and whether it necessarily means you can't also be a victim. Probably the most straightforward answer, within the narrative structure (as opposed to being a bad guy or the proper subject of resistance in the real world), seems to be you are the provider of the conflict. The victim is the one our hero must struggle against and overcome or at least neutralize. Cap refuses to engage the WS on these terms, he resists the WS's mission but isn't willing to attack the WS himself - which seems to say that it's that mission that provides the conflict and, if we need an actual person to be our villain, that's a more fitting role for the WS's boss rather than the WS himself.
So if a villain is the person the hero must engage and beat, I think the crowd that says the WS isn't really the villain of this story. But I'm not actually sure this is the definition spiderfire47 has in mind, because the point seems to be that we as the audience know something about the WS that most characters (pretty much everyone other than Cap) doesn't know. The WS is a trained assassin. He has wrecked probably hundreds of families. He may have a background that makes us sympathetic, he may even have a particularly intimate relationship with the heroes, but to those families who don't know that backstory, they would certainly view him as a villain. He is not someone who needs to be "saved" or redeeemed, he is someone who needs to be stopped. And probably made to suffer as recompense for their pas wrongs.
At which points I began thinking of other blond ex-army men who had a special relationship with assassins, and whose body counts, by the sheer virtue of the pain they've caused, seem to be villains. I'm a Sherlockian - of course my mind went to Mary Morstan. But I don't think this question is limited to that route. The fact is, pretty much all modern literature and movies give us heroes with backstories. Voldemort was once an orphan that Dumbledore failed to reach for whatever reason. We don't know a whole lot about Sauron's backstory, but Melkor's has always seemed pretty sympathetic in its way; it starts with the desire to create something of your own, and to exercise the degree of power and vision you have. If Melkor isn't a pitiable case look at Feanor, Maeglin, Saruman, even Gollum - in so many of these cases it seems like we're supposed to pity them or at least understand what drove them. There are very few orcs, very few purely evil characters without a backstory. And moving past Tolkien, Loki is more trickster than anything (and the daddy issues explaining that one are a little too understandable for my comfort...). Magneto has a very realistic fear of being singled out as different and exterminated, given his background as a camp survivor. So if the definition of a villain is someone who is evil, who is a bad person... all the villains that spring to mind for me seem to have rather similar characters to the good guys. They are as often as not villains because of situations they came out of or because the choices offered to our heroes weren't available to them. Imagine if Gandalf didn't have access to those years in Nienna's gardens, and the hobbits to remind him of the value of mercy and simple things; would he really have been any less cynical and willing to compromise than Saruman is?
All of which brings me back to Mary Morstan. She's a trained assassin. She has a very removed demeanor, with the hinting that she's done some truly awful things. If all it takes to be a villain is to have harmed a lot of people and caused a lot of suffering, then she seems to qualify as a villain. I'm fairly sure, though, there are other characters who have a longer list of victims attributable to them. Mycroft jumps to mind here; given the nature of his work, and the way he has to take a big-picture view, I can easily see a lot of "collateral damage, a lot of lives peripherally connected to bad guys destroyed in the course of his career in the name of the "greater good" - grieving families who, if they knew his name, would probably hate him as much as Mary's victims hate her. I keep coming back in my head to the difference between a sniper and an assassin. I mean, the military uses snipers to take out its targets, and I find myself wondering what we'd call someone who rather than targeting people identified by the government as folks who needed to die, went after targets she had decided for some reason needed killing, people like Magnussen? That would be an assassin, but very different in my book from a hired gun, someone who just killed whomever in exchange for a paycheck.
It's kind of like the difference between Chakotay and Paris on Star Trek: Voyager (I've been rewatching the first season so it's on my mind). Both are Maquis, both cause a lot of damage, probably to some innocent peopel and certainly to Federation interests. One is fighting for his homeland, the other for whomever will pay his bar bill, but both seem properly categorized as terrorists. From the perspective of the Federation and Janeway both seem to be villains, at least under that first definition. But are both equally villainous under the second? Do they both qualify as bad people? Does the mere fact that Chakotay is willing to attack ships and whatever else because his peoples' home was threatened make him operate any less as a villain to bystanders who only know the damage they've seen him do and how it affects him? Does whatever contributed to Paris's getting into that situation make him less of a villain, because the actions that landed him in jail were in some sense understandable in the context of a certain past?
With Mary's character, I'm not sure we know enough about her to really make any solid judgments, but say for argument's sake that she was trained as an assassin by the military and got disillusioned after being told to take out a questionable target, so she went solo and went after people who she thought (let's even say correctly thought) deserved killing - but that she was willing to accept a certain collateral damage consistent with what she would have tolerated in the military. Say she's only going after the Magnussens of the world, but if someone wanders into the scene like Sherlock did in Magnussen's office she'll kill them as well. Does that make her a villainous person, a morally bad person? I'm hard-pressed to say she's any worse than Mycroft in that regard, who seems content to let Magnussen destroy lives as long as they aren't too important. She's certainly criminal. Would a bystander think she was a villain, or the relatives of her victims (innocent or otherwise; I'm sure even Moriarty's dog thought he was a good master)? I'd expect so. Would she have been any less a villain if Sherlock hadn't walked into that office, or more of one if Sherlock had decided he had to take her down rather than work around her, assuming the end of HLV isn't some great ruse?
These are the questions that fascinate me. Also the ones that keep me up nights. If Mary is supposed to be a villain because the plot demands Sherlock somehow neutralize or beat her, if it's a good enough story, I can roll with that. But the whole concept of what makes someone a villain starts to get very contingent to me. It's all so subjective and seems to lack any real substance.
I don't mean to make it sound like there are no true villains or excuse bad behavior. There's a difference between being understandable and relateable and that making your action excusable. And so while I may sympathize with Melkor's drive to create something after his own design, I don't know that that justifies what he did after to try to do that, all the destruction and war he brought about. Actually, I'm pretty sure I do know: that was perhaps an understandable, but in no ways a justified, reaction to being told (essentially) to sit down and shut up. And while I may sympathize with this (hypothetical backstory for) Mary, I think the second you're willing to kill not just the Magnussens but the bystanders as well - that may be sympathetic, but not at all okay. Still, I find this idea that being a villain somehow excludes also being a victim a really interesting one.
As with most things, it comes down to what you mean by a villain. And that answer isn't always so easy to pin down as we might like.