"Remove Cover Art" should remove all Cover Art, including any embedded Cover Art ~OM~. I had to do some of that recently.
The returning Cover Art is a bit of a strange one though. My first thought is that you are not allowing MC enough time to edit all the files and remove the embedded image. Embedded Cover Art is stored in each file. You should see messages at the bottom of MC about saving tags, and you need to wait until tag saving is complete before closing MC. But that shouldn't take long if the files are local.
Anyway, if the Cover Art is wrong, why not find some correct Cover Art, then delete the bad stuff and add the good stuff. MC should save the new Cover Art correctly and hopefully that means the old Cover Art doesn't come back.
If that doesn't work you need to check your Cover Art settings, check if the Cover Art files are actually being deleted off disk and out of the files, and if you don't find anything, come back and tell us what your Cover Art settings are, and where you have them stored if externally, or if embedded etc. Windows Explorer will usually show a thumbnail image when a file is selected, if it has embedded Cover Art.