I have tried the paint pens, and even those eventually fade if they are in direct sunlight. So far the method that has been most permanent (and most readable) has been the industrial strength adhesive labeling tape that I can get for my brother label-maker. Some of mine have been in the garden for four years so far, and show no signs of fading or peeling. My zinc markers came with a black paint pen supposedly designed specifically for this use, and UV/fade resistant. Within a year, the fronts of those were unreadable. Thankfully, I'd also labeled the backs, so I was still able to read that side and make the printed labels for the fronts. I don't think you'd ever be able to remove the label to reuse the zinc marker plate, though you might be able to apply a new label on top of an old one. I think that would reduce the long-term life of it. I don't recommend these for perennials or plants that you'll replace often. They have been wonderful for my perennials and permanent plants, however!
I do use a regular pencil on my white plastic markers for my vegetable garden, and have to agree, it lasts longer than other markers or writing utensils.
