The easiest way might be to forfiet his account and use it to offset the next deposit.
Company writes him a check for the deferral. (or do a negative defferal if payroll company will allow)
Fix the W-2 with the payroll company to reflect no 401(k).
Adjust his withholding on the next payroll to cover the taxes that weren't taken.
Plan documents typically say that partially vested terminated participants forfeit the non-vested portion of their account upon the earlier of distribution or incurring 5 consecutive breaks-in-service. If this person had more than 5 consecutive BIS before the effective date of the amendment, he should not have any non-vested amounts in his account balance that could possibly be affected by the amendment. What does the plan say?