The carrier does not clear the missed call logs. The carrier clears the voicemail icon.
Have you tried clearing the "missed call logs" in "view folders?" Do you have missed calls set to show in the message list? If so, you may need to go to the message list and highlight todays date and select "mark prior opened." However, it may take a reload of the OS in order to clear this up. This used to happen on early Pearl OS's and a software upgrade/reload was what was needed. The missed call icons should normally go away when you go to the phone page.
I did everything you mentioned. I am on alltel and am running version 4.2.2.123. Is there a newer os than this? I have never reloaded an os before on the bb and didn't know if there would be a problem running a different one with alltel. Also, if I reload the os will I always have to do this to take care of the problem? Thanks