Recently I heard from a senior student that the celebrated adaBoost paper was originally rejected by a conference.
Are there any other instances of seminal papers (in any field) which initially could not warrant a publication?
I'm not sure if this counts, but Edward Jenner's original paper on smallpox vaccination was rejected by the Royal Society.
In 1797, Jenner sent a short communication to the Royal Society describing his experiment and observations. However, the paper was rejected. Then in 1798, having added a few more cases to his initial experiment, Jenner privately published a small booklet entitled An Inquiry into the Causes and Effects of the Variolae Vaccinae, a disease discovered in some of the western counties of England, particularly Gloucestershire and Known by the Name of Cow Pox (18, 10). The Latin word for cow is vacca, and cowpox is vaccinia; Jenner decided to call this new procedure vaccination. The 1798 publication had three parts. In the first part Jenner presented his view regarding the origin of cowpox as a disease of horses transmitted to cows. The theory was discredited during Jenner's lifetime.
One should also mention Fermi's famous 'Beta decay' paper, which was rejected by Nature and appeared in Z. Physik 88, 161(1934). English translation of the paper: http://microboone-docdb.fnal.gov/cgi-bin/RetrieveFile?docid=953;filename=FermiBetaDecay1934.pdf;version=1