From which sources do mobile caller ID apps retrieve caller names?
Public directories, e.g. whitepages.com.
If the number is saved in your contacts list, then usually the cellphone will display whatever that number has saved as the name.
If the number is not saved then your cellphone will use the public directory and display whatever name is connected to that number in the public directory, often there is no name or the name is hidden, that's why you'll see "unknown caller" or a similar message when you're called by cellphone. Landlines will usually have a name attached to the number.
Public directory is derived from user's contact list?
I guess it is from the contact lists. However, for example if you have your Facebook contacts synced in your phone, and the facebook friend also had his contact number entered in Facebook, even those info are picked up by the caller ID as it scans all the entries in your phone contact list.
and if names of same number are different in two user's phones?