If a ‘Mary Sue’ character, as by your definition, always succeeds, then would not the opposite of a ‘Mary Sue’, an ‘Anti-Sue’, be someone who always fails?
For instance an Anti-Sue, if contrasting via your definition of a Mary Sue VGROSSAK, would be someone who is not faultless, infallible, predictable, idealized or one dimensional. The epitome Anti-Sueness would be someone who constantly makes mistakes, has tedious flaws, and has an unorthodox personality with three dimensions. In addition one could say that an Anti-Sue is someone who has fundamental human characteristics instilled in their persona, thus causing them to have bad luck with fate, meaning that an Anti-Sue has practically a zero percent chance of conjuring up a Dues ex machine. To put it simple time and effort would be used to complete even the most basic of tasks. So in order to create an Anti-Sue antagonist, realism is needed to make the character believable, thus eliminating the Mary from Sue.
To answer your other question, ‘a villain who is so consistently evil to the point of boredom,’ I would probably say that…that it’s a Devil-Sue…?