How should I cite a conjecture to which no written record can be found?
"Which of these are most widely accepted?" sounds like you're asking a poll-type question, which is not quite kosher for this site.  I believe that the situation is sufficiently unusual that there is no "standard" answer.  Nevertheless I will say what I think.  

First of all I want to express some skepticism of the premise that the information that Conjecture (C) was made by famous, long-deceased professor E is an important to the extent that the work of the paper would be less interesting without it.  If Conjecture (C) had been well known to the community and many other people had worked on it and/or written about it, then its provenance would be key information: those who knew about the conjecture would make a clear audience for the paper and would vouch for the prestige and value of the work.  But if no one  -- or almost no one -- except S has prior familiarity with Conjecture (C), then the information that it is due to professor E becomes more of a piece of trivia / personal motivation for professor X.  If the provenance of the conjecture had really been a key motivation for X, then one wonders why X did not verify this before working on the problem.

Second I want to say that I think you are using "knows for a fact" in a way different from the way I would use it.  If S is "sure" about the provenance of the conjecture because he saw it in print once but now cannot locate that printed source -- then actually he is not sure, I would say.  Often someone thinks they saw a certain piece of information in print, but when they go back to check it turns out they did not remember it accurately.  In fact probably every working academic has had this experience more than once.  I'm sure S is great, but "S says it, and S can be relied upon" is not really convincing to me no matter who S is.  In a professional context, the things that one is "sure" about should be verifiable: if E is a famous mathematician, then it should be possible to get a comprehensive list of their publications, and then with sufficient effort one can look through all of them, including "obscure conference proceedings".

The way I would handle the situation is by first corresponding with S and making sure that S is completely comfortable with being attributed the claim that Conjecture (C) was first made by E: if this gets published, then S may get asked some questions about this.  If they are not comfortable I would go with something more mild like mentioning S in the acknowledgments.  If on the other hand S really insists that Conjecture (C) is due to E, then that is what X knows and X can put that in the paper in that form, i.e., something like


  Conjecture (C) was conveyed to me by S.  According to Professor S, the Conjecture was first made in a paper of E.  Unfortunately we have not been able to track down a reference."


I would also be prepared to get some questions about this from the editor or referee when you submit the paper.

Finally: have you asked about this on MathOverflow?  This would be a very appropriate question on that site: if the paper exists then someone ought to know how to find it, though you may not know nor even know how to find that person.  Even if the question does not get answered in this way, you (or X) can still point to it as proof of your due diligence in the matter.