I wonder if it would be possible to create a vector image format that could identify the shapes and paths that are critical for legibility, and then write a scaling algorithm that is able to produce crisp results at 16x16 from the vector source.
On the outset that feels like a really hard problem.
The starting point would be to look at font rendering, especially hinting. I'm not sure if any of the popular font formats allow for adding more strokes when rendering at larger sizes, so they may not have much ability to scale image complexity, but they definitely have what you need to optimize for legibility at small sizes.
At risk of sounding like the guy who throws the machine learning hammer at everything, I actually wonder if a tiny CNN would not be a great solution to this. If you have a bunch of example icons tuned for low resolutions, as well as the vector art, you could potentially train a network to do a better downscaling job specifically tailored for icons. The point would be that the CNN weights could be common to all icons and not necessary to store in each file. Since the "domain" of icon design is quite restricted in terms of dimensionality and colour space, I bet a pretty small CNN would do a great job.
On the outset that feels like a really hard problem.