I'm not sure exactly what your compliance requirement is (i.e.: ISO17025, etc..). But in general terms, your creativity is one of the main considerations.
I have seen a very wide variety of methods used. I had a lengthy debate with a quality manager (very knowledgable one, by the way) about why we even had to have the labels. This is ONLY my opinion. But theoretically, he convinced me that we truly did not absolutely have to have labels. What we had to have was assurance that measurements are properly traceable (with all implications that entails). So bottom line, you need a method to be sure that people using your gages only use calibrated ones. Or if it is the case that these are gages installed in a system, have a method to assure that people either only read them when they are in calibration, or whatever you intend for the use of the label to be.
One question that could be asked is what you actually use the labels for. If it is a reminder to users to turn them in for cal, you need a method to assure that that happens. What ever the purpose is for the labels, you have to have a good method to assure that function happens.
The most desirable method and the simplest to prove is to put labels on the units. It is possible that you could find some other way to make that happen.
All that philosophical input aside, I am still a proponent of using labels, as it is the easiest to implement. I had a plan in place at a previous position to associate calibration and due dates with a data base so that if a tech attempted to use any test equipment out on the factory floor, he/she would have to enter it through bar code or other means. And the system would not let the tech complete the maintenance with a past due item.
If you decide you are best off with labels, there are two halves to the decision process:
1. Adhesion of the labels. Do a little research into labels with proper adhesives for your application. There are labels with a variety of adhesives available for a variety of challenging environments. You could make labels without use of adhesives - hanging from the unit in a "luggage tag" style enclosure, for example.
2. Writing on the label. If the issue is with the writing coming off, think out of the box as far as methods to write. I recall there being some mil-std contracts in my past where we had to meet mil-std legibility requirements. In some cases we had to etch, others, we had to test out various inks.
Any way, hopefully the above may be of some help to you.