First, that kind of layout is problematic as much as any layout using a diecut and a defined border as you used; any tiny misalignment is more obvious. As you know, machines are not 100% precise or consistent.
But it's still possible to get those printed properly, it depends on your budget though.
The only suggestion I can give you is to either modify your design (probably not what you want) or find the best printer possible in your region. You can find an offset printer for this, a quality one will use quality providers for special projects if they don't have the machines for it. You can mention them you want a waterproof label. What might happen is they will get the stickers printed somewhere else and they might diecut them themselves. They will also offer you a guarantee of quality for the work of their own provider if the stickers are not printed on their own presses. And quality printers also often use modern machines; these keep their adjustments better throughout the run.
I don't know if this system exists where you live, but you can find a ISO-9000 certified printer and have on your estimate the specific requirement that the prints and the diecut must be perfect; if it's not perfect, you won't pay or they'll start the job again. You will be shown a proof that will be cut perfectly, and as you will approve this proof, make sure to write that the diecut has to be as perfect.
The quality printers will calculate on their estimate a longer time for more adjustment of the diecut machines and also more stock wasted to adjust the machines. So it will be more expensive for you but this is really the only way you can get a good result. The only other way is to modify that layout and avoid that kind of border.
Do not go to tiny print shop, agents, intermediary, copy centers, online printers, etc. They often don't have their own machines and shop around for the cheapest estimate. Go to a real one, visit the place if you have to.
There isn't much more I can suggest you, this kind of print shouldn't be an issue for a top quality printer. Obviously you got those done on offset and large sheets (unless your stickers are tiny), and the layout isn't that close to the edge. I can only blame the operators for this and yes, you're right to not be satisfied, it's misaligned.