Reg. 1.401(a)(4)-5(a)(3) is the 5 year safe harbor for grants of benefits for past years of service.

If one were to establish a new DB plan and not use this safe harbor (i.e. count all years of service prior to establishing the plan) the determination as to whether or not this has the effect of discriminating significantly in favor of the the HCE's is a facts and circumstances test.

Does anyone out there have any examples of successful demonstrations that granting more than the 5 years allowed under the safe harbor was not discriminatory?

Seen it. The testing included those who were employed during that service, even if not employed at the plan's effective date.

How was the test performed? More to the point, how do you test for discrimination with respect to people who are not plan participants and never will be?

Census data was collected and testing performed as if the plan had been in existence.