Is it possible under a safe harbor 401(k) Plan to have different eligibility provisions for deferral and matching contributions (e.g., immediate participation in regard to deferrals but year of service requirement for matching contributions).

Notice 2000-3 (Q&A-10) appears to permit this but also seems to require ADP/ACP testing....

You have to test the portion of the plan that does not comply with the safe harbor -- the participants who do not have a year of service. Because it is very unlikely that the tested portion will have any HCEs, it should pass. I assume that you are looking at the match as the safe harbor option, but it works the same same way for the nonelective contribution option.