I imagine that if you have 50K employee's and you are paying google ~50$/account/yr(2.5M/yr) (im sure if you had 50k employees you would work a deal out with google), you could work a deal to get the contact list thing straightened out.

1 User who says they are willing to pay is significantly different then a company who is paying for 50k employees.

Google apps already autocompletes on the employee list: http://www.google.com/support/a/bin/answer.py?hl=en&answ...

The personal contacts is another thing. So having 10k or more employees isn't a problem for google apps, what is a problem is employees who have more than 10k personal contacts (not very common).