I’ve deleted all of my recents and missed calls but it shows that I have voicemail; when I try to go into voicemail it says my mailbox is full. Same thing when I call into it from another phone.
On the bottom of your Phone app in the far right corner there should be a "voicemail" icon. From there you can delete voicemails, if that doesn't work I suggest contacting your service provider as they handle calls and voicemail.