Find all Untrusted but Enabled constraints
Estimate the amount of time each will take to test for existing rows in violation of the constraint (DBCC CHECKCONSTRAINTS)
Determine if that will go past the maintenance window or if it will take more time than any one operation is allowed; if it will go past, proceed to the next untrusted but enabled constraint
Execute DBCC CHECKCONSTRAINTS, if no rows, proceed, otherwise, record the rows (all of them).
Estimate re-trust (ALTER... WITH CHECK CHECK... which would render the DBCC a complete waste of time if it didn't batch abort when it finds a row in violation) time
Determine timing as above
Re-trust the constraint.
Time estimation done based on parms passed in until enough of a given specific operation has been done to use a cumulative average with a fudge factor.
This runs daily with tight time limits (no more than a few minutes total maintenance window, no more than a few seconds per operation) to reduce contention and locking possibilities within the maintenance window, and weekly with much more generous limits within a much larger maintenance window.
P.S. How many others actually set up jobs that stay within a known maintenance window (i.e. they're designed to do what they can within a window of time, but not exceed the window)?