GWT definitely doesn't show you the whole picture. Majestic SEO won't show you the whole picture. Ahrefs or OSE can't show you the whole picture either.
Google has a pretty good idea of your link inventory. They share very little. In my understanding, the spreadsheet you download is just what they've shown you until it's no longer there.
No one set of link data is ever 100%. It's a big internet, but the one source that appears to generally share the least amount of data is Google. That's why you should use multiple sets of link data and do some spreadsheet wizardry to sort out the duplicates.
The general consensus regarding how long it takes to get a link penalty lifted is; "It takes as long as it takes." Some have taken up to a year and a few turned around fairly fast. Four months isn't exactly irregular.
Majestic is showing a lot of deleted links, so there's definitely some progress there. It's just hard to see the wheat from the chaff at a glance. Yeah, the backlink profile was hit hard.
Regarding the 404s... letting them 404 is just wasting crawl budget. It may be a good idea to 410 those and let the bots know those pages aren't there. In regard to what pages were dropped, you might have lost some pretty good links. I haven't done a page level audit, but losing good links with a ton of bad can delay the process as well.
Someone is going to chime in about the 'foundation' of links, and they would be correct. It's a whole other screed - so I'll leave it to them. Seriously, this one looks pretty nasty. Best of luck.