How are others planning on handling the new US Oracle Payroll Tax Engine (USOPTE) rollout?

Our company has a very very large employee population and we are trying to determine the best plan to rollout the new US Oracle Payroll Tax Engine (USOPTE). It took us over 15 hours just to run the address validation process, so we are trying to determine the best plan to squeeze in that, all of the address corrections we will have to do, on top of tax validation and doing this all between payroll runs.