I am surprised majestic was missing links in a full report
Majestic honours the robots.txt protocol. So if sites block its bot, it won't crawl the site. Also, Majestic, although one of the best SEO tools ever, is sometimes missing the small sites residing in the deep realms of black-hat world.
There is one major tool your list is missing. If you google for
backlink tool it will be there on the 1st or 2nd page depending on which country you're googling for.
BUT There is a chance adding another tool won't help you discover more links because, strength-wise, they're all pretty similar.
In fact, I am surprised you're having to go through this because I usually find it's enough to combine Majestic, OSE and GWT.
One thing you can do, though, is search for your links using some advanced search queries... that is if the site's link acquisition efforts have footprints. I bet you'll find footprints.
For example, if the previous SEO guy concentrated on building "forum profile links" and used a certain set of anchor texts, you'd search for:
"buy green widgets" inurl:"space.php?uid"
or
"buy green widgets" inurl:member.php depending on which forum software is used on the spam sites.
If they've concentrated on doing link exchanges, you'd search for:
"buy green widgets" inurl:links.html
or
"buy green widgets" "exchange links" and so on...
Mind you, this only works if your keyword combinations or link description text are sort of unique. If it's just a one-word anchor text or something very popular, you won't get much out of this method. But I've had success with this method in narrow niches.
Also, something to consider. Maybe you simply have to "work" your current toxic link list better. Maybe Google thinks you haven't quite proved you've put enough time and effort in the whole link removal procedure.