Here are the guidelines about submission to STOC 2015 with regard to
submitting a prior published paper. I assume that most of the Theory Conferences have a similar policy.
Prior and Simultaneous Submissions: The conference will follow SIGACT's policy on prior publication and simultaneous submissions. Abstract material which has been previously published in another conference proceedings or journal, or which is scheduled for publication prior to July 2015, will not be considered for acceptance at STOC 2015. The only exception to this policy are prior or simultaneous publications appearing in the Science and Nature journals. SIGACT policy does not allow simultaneous submissions of the same (or essentially the same) abstract material to another conference with published proceedings. The program committee may consult with program chairs of other (past or future) conferences to find out about closely related submissions.
Here is a question that I ask non-rhetorically. What if Alice has a paper in arXiv in 2010 and submits it to STOC in 2012. Technically it has not been published before. However, it certainly is not new.
Should this be allowed? Under the current rules of course YES. Should the rules be changed? A paper can be out there without it being published. Should the rules be changed to reflect this? I think NOT since it might be hard to define carefully and I don't want people to discourage posting on arXiv.
Should the committee be allowed to take its not-newness into account in judging it? Do they already? And the notion of well known or out there are subjective.
BOB: This paper has been known about for years.
EVE: Well, I didn't know about it, so for ME its new!
There might be a newness/quality trade off. If Donna posted her proof that P=NP in 2020 but submitted it to STOC 2030, I think it would still get in. By contrast if Bob posts a proof of a good but not great paper that is STOC-worthy in 2020, and then submits it in 2030,, I think it would not get in.
Then again, by 2030 maybe we will have changed the prestige-conference model we currently use.