I consider a fact to be something that is verifiable or falsifiable by an outside party. If you can run an experiment or collect data to establish the truth of a statement, it's a fact. If you're left with "Well, how would you prove that?" or "That's not what I really meant", it's an opinion.

I did say that the Wikipedia statement was an opinion, but I'll take a stab at each of your examples:

"Bach is the greatest composer who ever lived" leaves open the question of what it means to be the "greatest composer". "No other composer wrote such great music as Bach did" at least defines what it means to be the greatest composer: there does not exist a composer who wrote such great music as Bach. It's still an open question what "great music" is, which is why this is still an opinion. But it's moved us closer to having a verifiable statement that we can test.

"The Mona Lisa is overrated" has a bunch of open questions: who overrates it, what should its rating be, how do you rate artwork, etc. "Most people rate the Mona Lisa's merits more highly than it really deserves" closes the first question ("most people" = take a poll) and makes the second two questions explicit ("Mona Lisa's merits" - like what? "than it really deserves" - well, what does it really deserve?) Still an opinion, but at least we have leads as to how to make it a fact.

"The Republicans want to feather their own and their benefactors' nests, and don't care about anything else." Here, the problem is that we're making a statement about someone's mental state, which is not verifiable unless you ask them and take their answers at face value. Both English and E-prime have this problem. BTW, if you accept their answers at face value and set some threshold for what percentage constitutes "The Republicans", this becomes a fact. Simply poll all Republicans and ask if they want to feather their own and their benefactor's nests. I doubt you'll get a truthful answer, but that's just my opinion. ;-)

"Barack Obama's success in politics results entirely from his persuasive oratory, despite the false impression to the contrary that he is careful to give" - that's exactly the sort of opinion -> fact transformation that E-prime encourages. "Barack Obama is a charlatan" is an opinion, because it doesn't define what a charlatan is. "Barack Obama's success in politics results entirely from his persuasive oratory" is falsifiable, almost: if he stops giving speeches and yet remains successful in politics, we know this statement is untrue. (There's still the open question of what it means to be successful in politics, though.) Unfortunately, I don't think we're allowed to run experiments on the president-elect's power base, so until we do, it might as well be an opinion. But we have at least pinned down a criteria for verification that we can use to determine the truth of the statement.

Something I noticed about all these examples - even if they're still opinions, the words they introduced raise questions about how to factually verify them. These are not wasted words: they indicate that there's a part of the argument that was omitted. It's like putting assertions in your code. They add needless verbosity and make your program crash, but that's the point - they alert you that you're not handling a case correctly.

On the remark: "perhaps they shouldn't" is obvious as opinion to me. "Should" is a red flag for opinions. "Arguably aesthetic judgements are matters of opinion rather than fact" is not, because it uses the word "are" to make a global judgement that can't be tested. I think that's the perfect example of E-prime clarifying an opinion-as-fact problem.