It sounds, like
@leejor said, that the phones that do not work right (the ones that show the wrong info - not the actual extensions of the new users), have not been properly
factory reset.
- This is the first step of troubleshooting. Always!
- Then firmware (make sure all phones have the latest 3CX firmware - not the latest vendor firmware!!!)
- I assume your PBX is running the latest and greatest
What do these users see when they use the app? I mean the users that their X4 shows the wrong info. When they use the app, what do they see?
- if they see the correct info, then the problem is 100% with your desk phones (if you have done the factory reset properly, then login to the phone web interface and check the PHONEBOOK
Check the CONTACTS that should be empty BUT!!!!! keep scrolling and look at the next screenshot about the cloud phonebook

Note here (in the cloud phonebook), you have a company and a personal phonebook (you can see both in XML if you copy the URLs from the table under MANAGE CLOUD PHONEBOOKS)
Check these and delete if you have already done a factory reset and they are still there

My bet is the above - stuck entries on the desk phone.
- if they don't see the correct info in the app, I would try the following:
- impersonate the user extension that sees the wrong info (again - not the new user!!!) - go to CONTACTS and check ALL contacts (personal and everything should show up there)
- Also just in case, check here? https://YOUR_FQDN/#/office/system/contacts
Hope that helps