In Call Logs, select the contact and delete it. That will delete all occurrences of the contact in Call Logs.
In Messages/Menu/View Folder/Phone Call Logs, deleting one occurrence doesn't delete them all. At least, I can't find a way to do it. You can select a range of calls by holding down the left shift and scrolling, but that's only helpful for multiple adjacent contacts. Maybe somebody knows a better way?
