Okay. First things first. Do not mark your 404 as being fixed. You are actually prolonging the issue. Google will try and fetch a page that returns a 404 several times before giving up. This is because the 404 error indicates a temporary situation where a 410 error says the page is gone. So every time you mark a 404 as being fixed, you are in effect telling Google to try again thus starting the process of elimination all over again.
Just let these pages 404 for a while and Google will stop looking for them and will drop the pages from the index. It will take time, but short of a 410 error, this is the easiest way. A 410 error would make the process faster, but it is harder to present a 410 error and a 404 is the default making it the easier and natural solution.
Your removed pages will disappear in about 30-60 days if you can wait. It depends on how often Google visits your pages. It can take longer, but once 404's are found, Google likes to first spot check the site, then depending on how many 404's there are, may spider your site more aggressively.
Using a sitemap actually does not generally fix any problems with the index. It only makes life simpler for search engines. It is never taken as the be-all end-all list of pages any site has. If a search engine reads a sitemap and still finds pages not listed in the sitemap, it will continue to index those pages.
One option if it makes sense to do, is to list these pages in your robots.txt file. If there aren't too many (meaning something you can do and your robots.txt file would not be too long), that would be a faster solution. Otherwise, I would just wait and let the 404 errors expire on their own.
One last word. You will be okay. Really. It will all work out very well for you if you are patient.