I have been happy with my current Brother PT-P750W and its labels. Not sure if you're looking for a label printer that requires a computer, but this one is wireless and even runs on AA batteries if you want. I really enjoy being able to make nicely-formatted labels in any font I want with any graphics I like.
I don't have any knowledge about the amount of stickyness of the labels themselves, and how they compare to the Dymo labels. And of course the plastic on the surface of your new hardware devices is really the biggest factor - there are some surfaces that no label will stick to, like certain textured-surface plastics are gonna be a losing battle no matter what. So I don't know if Brother's labels are any stickier than Dymo labels in that regard, so I don't know if they'll solve your problem. I know that I've been happy with mine.
Tahir's suggestion of double-stick tape is valid, but, the whole point of using a labeler is to avoid that extra fiddly step of having to cut out double stick tape of the correct size. Plus, ordinary double stick tape might end up having the same problem. Most ordinary double stick tapes that I've used are very non-permanent and only barely stick. You could use Gorilla brand double stick mounting tape, which is the only one I've ever seen that actually sticks. But that's very thick, very gooey, hard to cut into the desired shape, generally difficult to work with, and would be even more hassle. It would fscking stick though, that shit is crazy.
You could use glue to ensure the label sticks. A drop of CA or Gorilla glue or something. Again, this is much more hassle, and also negates the convenience of using a labeler in the first place.
An idea: Go to an office supply store and get a few different brands of just the label refill cartridges for label printers, and try them out. Just peel them out of the cartridge, blank, cut off a section by hand, and stick them on your NUCs and see if they hold. Then buy the label printer whose refill labels stuck the best. Or maybe there's a product comparison review out on the internet where someone already did that? Googling for that sort of things is difficult, I can't get the search terms right.
Ooo, here's a thought. I've never done this but I just thought of it. Try some regular tape, not labeling tape nor double stick tape. I've seen more variations of regular tape which have very strong stickyness, than I have of double stick tape. If none of the labeling tapes stick, find a regular tape that sticks and has a smooth outer surface. Maybe you can even find a color that matches your NUCs (black I'm guessing?). Not electrical tape since it doesn't stick to flat surfaces well, but maybe something like black-colored duct tape, or maybe there's even better tapes out there, such as tape made for outdoor use, that might be really strong. Then just slap some that on your NUCs, and then stick your labels on top of it. If you can't find labeling that sticks, but you can find regular tape that does stick, this would be the least amount of hassle I think.
Finally, one thing I always do when I've got situations where labels might not stick as well, is, before peeling the stickyback off the labels, I quickly trim a tiny amount of the pointy corners off the label with scissors, so the label becomes an sort of an octagon instead of a rectangle. I've found that if the corners of the labels don't have a pointy bit, then accidentally brushing against the labels doesn't cause the corners to "catch" and peel up and make the label fall off prematurely. This is still more hassle than just printing a label, but it helps in those extreme situations, like, labeling the outside of a portable equipment case that's going to see a lot of usage and having stuff brushed up against it. If you know of a label printer that does this automatically, let me know, I might buy it.