This reminds me of the numerous people who have similar problems with their SMS/chat messages in the Conversations app. I suspect call logs, just like the Conversations, are stored in an sqlite3 database somewhere.

If Nokia's implementation screws up the convo storing under some odd circumstances, it would make sense that every once in a while, same would happen to the phone logs.