This is where the 37 signals folks would politely say no. You can't please every user, and something tells me that a majority of gmail users aren't sporting a 10k contact list.
In this case, allowing 20,000+ contacts does not reduce anything for the rest of their user base; it only positively impact some heavy (and presumably loyal) users of their system, which nets in total increased satisfaction.
If the goal is to maximize overall total satisfaction, Google should engineer their system to support maximally conceivable number of contacts.
This is oversimplification. Knowing google, they would want to track different users' contacts and mutual contacts, and email frequencies habits etc. Contact size, is larger than O(N) complexity.
Yes, but the graph is very very sparse.
Edit: See http://www.google.com/support/a/bin/answer.py?hl=en&answ... I don't think user profiles (that would be what is used for employees inside an organization) and shared contacts have a 10k limitation, only the user personal contacts have it.
Instead you decide to be a jerk.