Can anyone explain why there would be a limit to contacts? My best guess was to prevent spam: 10,000 contacts is probably in the top 1% of users, but might be much more heavily seen in bots.
Side note: Gmail offers a "Most Contacted" feature to show you who you email the most. It might be interesting if they had a "Least Contacted" feature as well, to be able to easily remove contacts you never use.
Because it is based on BigTable and it has certain limitations designed to make it easier to implement, including a limit on how many elements one can return.
Also, 10k contacts is properly far more than most people would ever have so it is not a big deal.
Gmail contacts sync with mobile phones like the G1 which don't have tons of memory or processor power. Try using one of those phone with 9000+ contacts and its not a nice experience.
The limitation is there for performance reasons. Besides why is your sales guy is using gmail as his crm?
It is possible they made the limit to "protect" you from timeouts caused by performance limitations. Perhaps the contact system is still working with a weak indexing system, or maybe they send all the contacts to the browser in one giant JSON response.
Side note: Gmail offers a "Most Contacted" feature to show you who you email the most. It might be interesting if they had a "Least Contacted" feature as well, to be able to easily remove contacts you never use.