In use since the earliest days of CD-R, paper labels have been controversial since then. One worry is whether the adhesive and paper itself or even the ink applied to it is acidic or corrosive, and will eventually damage the media. This question arises because in the very early history (20 years ago) of compact disc, some discs experienced what became known as "disc rot" when the aluminum metal layer corroded because the lacquer used to coat it was acidic, making it non-reflective and thereby useless. While acidic lacquer is no longer used, it is still possible for the lacquer to be incompletely applied or for it to be damaged or interrupted by scratches or abrasions.
Certainly it is not a good thing to have any part of a disc carelessly damaged, but with CD-Rs that use gold for their metal layer, the danger of corrosion is extremely limited -- gold doesn't rust. However, the metal is applied in a very, very thin layer, and conceivably over time some leakage of a corrosive substance might occur that could interact with the dye layer. (This is pure conjecture -- no one has reported such an occurance and it may not even be theoretically possible). But with metals other than 24K gold being used in CD-Rs now, such as in Verbatim's DataLife "blue" media, the chance of metal corrosion, while still low, is higher than with gold. That is one reason Verbatim chose to use a protective "printable" coating on their discs, even though it is not as aesthetically pleasing as simple lacquer. However, it is possible to use paper and adhesives that are acid-free and chemically non-reactive.
Another concern about paper CD labels and their adhesive is the danger that a user might try to remove them, which has a very high probability of causing damage by pulling some of the disc protective coating, metal and dye off with the label. This is particularly true of plain lacquer discs, those without an extra protective coating. For this reason, label users are usually warned not to remove the labels, no matter what. A somewhat contradictory argument is that labels could become unattached while being used in a CD drive, potentially damaging the drive. Some adhesives can certainly dry out and become less effective over time, especially in the presence of heat, so this danger could be real.
With higher speed CD drives especially, a paper label that is not perfectly centered, or is inherently unbalanced as in the case of a half-crescent label, is thought to be the source of unacceptable perterbation in the disc rotation, causing read errors. It could be argued that this is not really the case; an experiment with a small coin taped to one side of a disc showed that it could still be played successfully. However, the general perception among users is that imbalance is a bad thing, and this argument is cited against the idea of using this labeling method.
But despite all the arguments against using paper labels, they are very popular. There are several reasons why, the primary one being cost -- paper labels are quite inexpensive, costing only pennies per disc, and if printed in a laser or inkjet printer they can look better than handwriting on the disc using a pen. A full-circle or "doughnut" label applied with a tool to center it perfectly eliminates any potential danger of imbalance. And a full-circle paper label provides a small measure of protection against minor scratches on the delicate top surface of laquer-only coated discs. If the labels used are chemically stable, and especially if the disc is used infrequently and is only intended to last a few years, paper labels are probably an acceptable method of identifying discs. But using paper for serious long-term archiving is not recommended by the ANSI IT9.21 standard because there have not been any controlled tests of this medium with paper labels over long periods or in accellerated aging experiments, and paper labels are warned against for other media because of some of the other dangers cited above, especially concerns over possible disintegration of the label after an extended time or potential interaction with the media itself.
The general conclusions that can be drawn about paper labels are that those made with appropriate materials in a full-circle and applied correctly are probably acceptable for short-term intermittant use, they are inexpensive and can be attractive, and they might give some protection against small scratches. But if you plan to use your CD-R disc for long-term (5+ years) archiving or for very heavy use, such as keeping it in a reader where it could be exposed to elevated temperatures over a long time, it would be better to find another labelling method.
As a bonus for those who have decided to use paper labels, we have started a collection of templates to be used for printing designs using various programs and popular label dies.
A number of companies offer labels for CDs. We've heard from Zweckform, a company in Germany. [Link updated 8/7/97] Thanks to Detlev Rackow for telling me about this product, which includes a plastic positioning tool. Unfortunately, his email address didn't work when I tried to thank him personally, so I hope he reads this and knows I appreciate the tip. Also thanks to Inge Bachner of Zweckform for keeping us informed about the URL to their English language webpage that includes their CD labeling products.