Sempre que você vir uma imagem com algo diferente de 100%, algo chamado filtro deve ser aplicado para produzir os pixels que você vê na tela a partir dos pixels da imagem.
Filtros diferentes têm propriedades e desempenho diferentes. Alguns fazem as imagens parecerem mais nítidas, outros menos, alguns funcionam melhor para ampliar, outros para diminuir. Existem facilmente dezenas desses filtros (com variações) e o tempo necessário para aplicá-los varia.
Vários aplicativos, como o Geeqie, permitem especificar qual filtro aplicar como um compromisso entre qualidade e desempenho. Quando você redimensiona (AFAIK não para aumentar o zoom) e a imagem no Photoshop, também existem várias opções que você pode experimentar para ver as diferenças. Máquinas modernas também podem usar a placa gráfica (GPU) para executar filtros sofisticados com extrema rapidez. Apenas alguns softwares aproveitam isso (se a máquina pode fazer isso), mas cada vez mais o fazem.
Portanto, para responder sua pergunta, o MS Paint parece estar usando um filtro com propriedades de nitidez no sistema. Observe que coisas como nitidez e redução de ruído também são tipos de filtros, a única diferença é que eles produzem o mesmo número de pixels que obtêm.
