A safe harbor 401k plan had a 6 month 401(k) eligibility provision, but incorrectly applied a 2 year eligibility period on participants from getting the safe harbor contribution. They want to go back now and deposit safe harbor contributions for everyone they missed during these affected plan years. They would include lost earnings on these contributions correct?

That would be a safe approach, to contribute whatever is necessary in order to have the participants be in the position they would have been in if the error had never occurred. What may complicate this is if the matches would've been invested in equities if they were done in a timely manner - should you reflect market losses? Probably 'yes'.

I've got a similar issue with an employer that did not contribute as much as employees elected (it did not reduce overtime), so the employees got more take home pay, and less 401(k) contribution. The employees didn't complain, but the accountants are insisting the employer make an additional contribution with respect to the overtime.

The plan has had investment losses, of course, so an earnings adjustment would mean contributing less than the make-up contribution. That seems to be OK under EPCRS, but there is no specific example in Appendix B for a case where there were no investment gains.

Bottom line, if assets lost 10%, can we restore just 90% under EPCRS, or is there an IRS requirement somewhere that the restoration must always be at least equal to the principal amount?

You can, but are not required to, adjust corrective deposits for losses. See Rev. Proc. 2008-50, Section 6.02(4)(a).