I make my own labels by writing the name and date on a post-it note (color coded by year), cutting it to a small rectangular size to fit my writing, and then scotch taping it to the centrifuge tube. I've been doing this for a few years now and the tape holds wonderfully in my freezer. And I get my centrifuge tubes from USA Scientific (#1615-5500).
Please excuse the incredibly blurry shot -- my camera is refusing to focus today...
But hopefully this gives you an idea of what it looks like -- if you can get past the blurriness, that is...
I also use the storage boxes that have each slot numbered, and I keep a listing of where everything is by variety. So I don't have anything written on the lids of the tubes. That way when I want a particular pollen I just go to my listing to look whatever I want up to determine its location. And I have quite a few boxes and try to replace the pollens each year. It's ending up being quite a task to record everything, and I usually use very little of my frozen pollen, so as things get more complicated I think my pollen freezing will be the first task I let go. But for now...