Hey
@bharris
If you are using royal mail then weight isn't too big of a problem because you can use average weight in OBA and potentially in DMO. However if you are using other carriers, you have to be exact or they will revenue protect (billing you the correct amount). Some carriers dont mind because they weigh and measure every package anyway. The only way to get weight and dimensions automatically without manually doing it yourself or pulling from a data source would be commercial equipment using lasers.
If you do have a range of SKUs that you ship out consistently, then I would use an order management system that can store dimensions and weights of final packaged amounts and then can auto generate the shipping label with all the correct information. Given that you have 1000s of various products, I'm assuming you make the most profits from only a small set and I would start here given that your profits are healthy and the orders are consistent. The long tail of other skus, you may want to address over time (doing 10 new skus a day), instead of doing everything in one go.
Shipping MULTI sku orders is very difficult to get right, even amazon, sends boxes too large for items sometimes. this usually requires a warehouse guy to with experience to see what is the best way to save on volume.
How I've gotten around sticking the wrong shipping label over the old one is by having more information on the shipping label itself. So we include: Order ID, sku, quantity, warehouse location and various other custom fields depending on the SKU.
These added fields on the shipping label first mitigate mispicks and mispacks but also helps when we need a brand new shipping label and makes it that much easier to identify the right one to overlay with the new label.