When you say “old-school”, do you mean the ones with raised print?
I use (and see a lot of others using) the Brother P-Touch type labels, either from a handheld digital label or a standalone label printer that uses the same tape.
As far as glue goes, I’d be worried about using any type of glue on the top side of the PBC. In theory, whatever glue is used on Velcro or 3M Dual-Lock should clean off (with some alcohol or goo gone and a bit of elbow grease), but I personally would just get another label printer. My PBC has gone through 2-3 relabeling efforts in the 3 years I’ve had it and haven’t had any issues with the P-Touch labels.