Following the answers to this question that it is quite common to inadvertently reinvent the wheel in theoretical/computational research, have there been cases where the decision to accept a paper to a journal/conference has been revoked on this ground, because someone found out later that the results were not actually original? In such cases, how would one distinguish between oversight and plagiarism?
By "revoked," I assume that you mean retracted. I have often heard of papers being retracted for plagiarism, but never for reinventing the wheel.
I believe that the reason is, there are so many different ways to invent wheels, that it is almost always possible to tell if an idea is actually an independent invention. A reinvention will likely use somewhat different terminology, have a different formulation of the problem, use different types of evidence, or whatnot. There will be so many small differences, that it would be clear that the work is original, in the copyright sense, and not an academic fraud.
The fact that is it a reinvention of an idea that was already discovered elsewhere, however, means that it is likely to sink into obscurity once this fact is discovered... except... sometimes, a reinvention is not just a reinvention. Sometimes, the reason for a reinvention is that an idea has not reached a community. In that case, the contribution may not be the reinvention, but the importation of a mature body of work from elsewhere, in which case even a reinvention of a wheel may constitute a legitimate scientific contribution, in the form of bringing together two strands of research that complement one another and allow vital new progress to occur.
jakebeal answered most of the question just great, but I would like to comment on this a bit more:
how would one distinguish between oversight and plagiarism?
I think this is no big issue in practice. Typically, people start talking about plagiarism if and only if the similarities (text-wise, or, in rarer cases, idea-wise) are so substantial that it would be very unlikely for the author(s) to have arrived at their text without knowing the original. When authors honestly have "just" re-invented the wheel (as it frankly happens all the time in research), it is very unlikely that the end product would be so similar that they get accused of plagiarism.
This may differ from computational work, but the concepts overlap, I think. In experimental science, it is traditionally expected that a published contribution is original, to the extent that you often have to sign a document essentially claiming originality upon submission. However, for numerous reasons (nicely explained by John Ioannidis at http://dx.doi.org/10.1371%2Fjournal.pmed.0020124, and cited 2400+ times!) replication of work is valuable in the sciences. We all have biases and make mistakes. And it is literally impossible to control for everything that may affect the outcomes of your experiments. So doing the same thing someone else has already done is actually a really nice validation of the previous work. It can demonstrate that two (or more) investigators have done the same or similar experiments and (hopefully) arrived at the same conclusions.
The original work will probably remain the exemplar of the phenomenon explained and garner all of the citations. But the "me too" experiment will make everyone who comes after more comfortable that the phenomenon is a real thing and not just a statistical fluke because of the weather on the day of the experiment or someone wearing cologne or forgetting to wash their hands.