Is it possible to run a Trace and identify all of the existing code that violates the constraints to be added? If you have a QA server with comprehensive automated scripts for regression testing it might be possible to identify all areas of the code that violate the constraints. If not maybe a sampling of production over a period of time will be sufficient.