How can I label cryotubes in a way that eliminates the problem of legible hand-writing?
This is indeed a problematic point. I have been using machine printed labels for a while now (sometimes with some extra scotch tape around it to prevent it from falling) off, which worked pretty nicely.

However, there is a printer available on the market (though I haven't tested it yet) which claims that they can print on any tube. This printer is called Tubewriter, which is probably also worth a look. The backside is the price, Fisher Scientific lists them around 40.000$, which will make them unavailable for most labs, except for cell banks etc.