Hmm. Next step is to see if the Windows repair utility can find any issues; from Control Panel > Programs and Features, click each of the "Microsoft Visual C++...." entries in turn, and for each one that displays a "Change" option in the top toolbar, click it and select "Repair" in the popup window. The repair utility will verify if the files match the installation fingerprints. Note that the very old libraries (VC++ 2005 etc) don't have a Change option but After Effects isn't using those.
In rare cases the VC++ installer decides to completely ignore the x64 library. There is a manual workaround that involves halting the VC++ installer halfway through and copying the files from a temporary folder; see the reply here by Michelle.
Failing that, it's looking like a complete re-install. Sorry.
Repairing all VC++ versions that I could had no luck. (2010-2017)
In the post by Michelle, none of those images in the instructions appear, so it's a bit hard to follow.
I can't find the temp folder the VC++ installer creates in C drive.
Alright, scratch that, I did something different.
I went into system32, deleted MSVCP100.DLL, and reinstalled it using the VC++ installer. It worked.
Not entirely sure how that was different to having it uninstalled via Programs and Features, but I'm not complaining.
If someone could further explain maybe why this worked the way it has (for future reference / others with similar issue) that'd be great.
Will post here again if anything changes.
Thanks for the help Dave Merchant. Would not have even known where to start without ya.