If your webmail is full, those emails are LOST! If you are cleaning your emails using a MAIL CLIENT, that's useless as well. Login to Cox WebMail and start deleting from there, making sure that after every few hundred, you go to the trash folder and empty IT as well! Last, at the bottom of the list of folders on Webmail you will see something that says personal folders or MY folders, or something like that. Open it up and look for deleted items, deleted messages, Deleted, JUNK Spam, etc etc, and ensure you empty THOSE folders, and then go back to the trash folder and empty it. Combine this with ALL the info everyone else has provided.
First thing I would do is forward all your email to a different provider while you work this out. That way you don't lose any additional emails. Next, If emails aren't deleting properly, you might need a ticket open for your account. Email Cox at firstname.lastname@example.org with your account info and the link to this thread. Let us know how it goes.
When I see posts like this my first question is usually, are you an Apple device user? Very often, Apple Mail will create it's own deleted items folder which is not the same as the one recognized by the Cox mail server. When this happens, the Cox mail server assumes this is just another personal folder for storing items you wish to keep. Simple solution would be to empty your deleted items folder after deleting emails.