Hello,
From the description it seems like you have not configured LDAP sync on CUCM.
Can you confirm which CUCM version you are using ?
From the SRND LDAP sync on CUCM : http://www.cisco.com/c/en/us/td/docs/voice_ip_comm/cucm/srnd/7x/uc7_0/directry.html
Instructions for doing the same :
http://www.cisco.com/c/en/us/td/docs/voice_ip_comm/cucm/admin/8_5_1/ccmcfg/bccm-851-cm/b02ldsys.html
You mentioned you already have LDAP sync enabled for your domains in Prime Colaboration Provisoning. Once you have LDAP sync enabled on CUCM, in PCP under Design > Infrastructure setup > Pick the CUCM and make sure the LDAP integration is not set to NONE and is set to either Sync or Sync And Authenticate.
This way when a new user X is created from LDAP, that user X comes into PCP. Now PCP will check if that user X exists in CUCM and only if the user exists, the services provisioned are added for that user. If that user is not found then PCP will wait to find that user in CUCM. So the sync schedule is important to make sure CUCM has the user X before Automatic Service Provisioning is triggered for the user X.
More details on Automatic Service Provisioning here: http://www.cisco.com/c/en/us/td/docs/net_mgmt/prime/collaboration/10-0/provisioning/guide/Cisco_Prime_Collaboration_Provisioning_Guide_10/Cisco_Prime_Collaboration_10_Provisioning_User_Guide_chapter_0100.html#concept_9E797ABECB524080977B08E22793B2C3
If you set the LDAP integration to None under Design > Infrastructure setup, PCP will create that user as Active Local User in CUCM and that is what is happening in your case. You can enable LDAP sync for CUCM and depending on the version of CUCM, those active local users will get converted to LDAP synced users automatically if the userid matches.
Hope that helps.
-dilip