what about this >>>>.
Can you delete from messages>fiew folder>missed calls or phone call logs.
And then go to home screen and press the GREEN button on your phone...see wether the phone calls logs really are deleted there.
Because with .344 and .321 they are not deleted. you have to sort of delete them by pressing the GREEN button (open the phone call logs) then delete manually from there.