FranticFish, if I'm understanding your situation, this is a domain you or a client controls, and you want to check it out thoroughly before rebranding, to get rid of anything that might give you problems later on.
I'm thinking that, in effect, this situation may be essentially the same as doing a pre-emptive disavow analysis. If it's not, then I'm still not understanding your question.
If it is, I myself would strongly recommend Majestic, as if you were using it for an unniatural links analysis... and I'd use it together with GWT. You've described why you don't want to use GWT alone, but for fresh links, as I remember, GWT can include links you won't find elsewhere.
That said, in my experience, Majestic (at least several years back), could spot backlinks for sites which I did not control, and spot them much faster than the competition could. To me, this suggests that (apart from Google) it had the freshest database. I can't comment, though, on, eg, ahrefs or moz now, because it's been a while. Majestic should have the oldest pubicly available database, as it's been around longer than the competition. I haven't kept track of which tool suites license Majestic's data and what they do with it.
It appears that you don't want to end up paying for more functionality than you need, which is very understandable. I should point out, though, that any complete link database is *necessarily* going to have data about links going both directions, as that's what they see when you spider the web. Even if you're not searching now for link building possibilities, some of that data about sites at the other end of a link to you will be useful for your purposes.
Majestic's Trust Flow and Citation Flow, while different from Google's PageRank metric, might arguably be more useful to you in deciding which links to you are the most valuable, and indicate which pages you want to keep and which you want to drop. They are metrics that I trust have been designed with many thoughts beyond the spammy link building norms of ten years or so ago, which "algos" until recently the competitve tools were emulating... and Majestic reports sitewide links, overly aggressive anchor text, etc.
For a while, when Jim Boykin became owner and custodian of WebmasterWorld for several years, we had the use of Jim's disavow templates, and I think I remember also his backend analysis flagged things like an overabundance of .ru and .cn TLDs. I don't know how much of this Majestic does now, but if you can group sides by TLD, they shouldn't be hard to filter. In general, let the Google Historic Data patent plus your experience be your guide.
Additionally, coming up if not already here, niche specificity and various kinds of trust metrics are factors you will need to consider in linking.
Tne days of repurposing expired non-profit dot orgs to become portals for job lead sites, eg, is, I hope, long gone.
I should mention also that way high up on the list of effective tools is the Link Dtox tool from Christopher C Cemper's Link Research Tools. It may be overkill for what you're doing, but if it's the basis of a rebranding it may well be worth it. I've never used this tool, but it's got an extremely good reputation among people I trust.
As for the subscription model, which works for agencies but can be difficult for solitary SEOs, that's mabye another discussion, but it's a problem for me as well, so I do understand.
