Way to many people assume the uncertainty of the measurement is some how tied to the specification of the UUT. It is NOT and has nothing to do with it.
The uncertainty is basically an estimate of how good the measurement/calibration is. In this case, the environmental conditions (temperature, vibration, air movement etc) may be causing the UUT to drift around. This drifting is but one component of the overall uncertainty. The resolution of the UUT and the standard, the charted value OR the specification of the standard, the uncertainty of the standards calibration are a few others that should be included. However the specifications of the UUT only come into account when determining pass/fail criteria.
ISO-17025 requires that the lab must take uncertainty into account when making a statement of compliance. Unfortunately most calibration service users require a statement of compliance to some arbitrary specification. ILAC has offered guidance on how to do this but the end users are woefully uneducated in these requirements, thus most labs tend to make the pass/fail call based on the unmodified measured value vs. the specification, then leave it up to the user to determine if the uncertainty is adequate for their needs. Because this lab was making a statement of compliance they should have contacted you and stated they could not meet the generally accepted TUR requirements based on the assumed tolerance of 0.01g. At that point you could have told them that you don't need it that tight and you could adjust the tolerance as needed for your process.
It is incumbent upon the user to understand their process requirements and the associated measurement equipment, and then be able to review the bona fides of the lab and determine if they are adequate to the task.