My position, depending on the type of deviation we are talking about, is that if the deviated part is acceptable, then you should be looking hard at the original design drawing to open up tolerances or make modifications to the design wherever possible. Tight tolerances cost money, not just in original machining time, but in scrap rates as well. If the deviation works, why would you want to make the manufacturer jump through hoops that are not required. Let us not loose sight of the ultimate goal, make usable parts and make money. if the part fits or can be made to fit, then trying to make a vendor jump through his butt is a waste of time money and resources. Tight tolerances do not mean good quality. MANAGED tolarances do. This is the error that many American Automakers fall into.
All that said, If the part can be made usable with either rework, or repair, or would work with selected mating parts (selective fit), AND the part or sub-assembly is serialized, then it is acceptable to generate an engineering deviation acceptance document and make sure that that serial number is trackable in that manner. Otherwise you need to either modify the drawing or reject the part.