Since CUCM is going to sync the LDAP users to it's local database, it will all depend of the server utilization. When a user searches the directory on the IP phone, it is using the directory the Publisher by default. If the Publisher has enough CPU and memory, etc it should be fine.
Are you syncing for authentication purposes in CUCM or are you syncing LDAP for phone directory ?
If you are doing phone directory only, I would suggest with that many users looking at a third party tool like Citrix Application Gateway. The "Express Directory" allows you sync multiply LDAP source and create custom directories for the IP phones. It's pretty slick in large LDAP enviroments, etc.
Cheers