I was about to scale this image down to 64x64 pixels:
The result I got on MS Paint on Windows 7 was surprisingly good (i.e. crisp edges):
I have also written a small program to check all of the interpolation modes available in the System.Drawing.Drawing2D.InterpolationMode enumeration, to no avail. Unfortunately, most web search results on the topic of interpolation in MS Paint are still from the days before Vista, when nearest neighbor was the only option.
Does anyone know which interpolation algorithm the Windows 7 version of MS Paint uses?