If a rehire repays his benefit distribution in the same year as the distribution is a 1099-R required at all? if so how do you treat his repayment? What if the repayment occurs in a subsequent year?

Yes, a 1099 should be issued.

The repayment could be made in pre-tax dollars (e.g., IRA rollover), or it could be made in after-tax dollars. In Q&A sessions, IRS reps have opined that a plan should accept both. (While the repayment doesn't cause a 401(m) issue, it could be problematic from a tracking standpoint where a plan doesn't otherwise accept after-tax contributions.) Someone could try writing a plan that limited payback to pre-tax $$ to see what the IRS would say.

So we issue a 1099R for the original distribution and the participant pays taxes on it. If he repays in after tax dollars, do we then have to keep track of that after tax repayment and deduct it from his taxable distribution when he finally quits for good? Or is he double taxed?

Yes to the former.