I fear I can't reproduce your issue, or just don't get what you mean exactly.
I've played around a bit and got the following call log:
Explanation:
- are several incoming (missed calls) and outgoing calls from/to a known contact (present in the phone book),
the correct number is shown and could be called from the phone log properly.
- is an incoming call from a known landline contact (present in the phone book),
but with withheld number (through the provider). Same would happen with withheld cell phone numbers.
- is an incoming call from an unknown contact (not present in the phone book),
the correct number is shown and could be called from the phone log properly.
- are incoming (accepted calls) calls from another known contact (present in the phone book),
the correct number is shown and could be called from the phone log properly.
- is an outgoing call to an unknown contact (not present in the phone book),
the correct number is shown and could be called from the phone log properly.
I don't had such problems on my Samsung I9100, neither on 4.2 0003 nor on 4.2 0004.
But I have to say, that I don't manage my contacts (phone book) on my Replicant device. I create a vCard (v3.0, with all of my contacts) and import this to my Replicant contacts by simply open the resulting .vcf file with a file manager.
Because you could double-import your contacts that way, I [Clear data] from the system-app "Contacts Storage" before I import the vCard again, (on contact changes or something).
I can't say, if this is responsible for a better behavior on my device, but I thought I should say that fact.
By the way, if you create "BDAY" values, too, you could keep track of birthdays of your contacts with apps like:
Sorry that I can't help here, yet.