I use a Brother labeler with 1/4" tape. With a little practice on how long to cut it, it fits perfectly in the cap, usually stays there when I flip it over to press the cap onto the key. Doesn't take very long, looks very nice. No tearing and folding. I don't peel the backing off either to keep the sticky stuff form working its way under the key.
For the phone number of the set (NPA.NXX.XXXX), I use 1/2" tape, but I think 3/4" will work better.
I like lableing the 3904s better. Takes no time at all!