A solução foi usar um editor de registro, no meu caso, o OO Registry Editor, procurar por string de tinta e excluir cuidadosamente tudo relacionado ao paint.net.
Cuidado, porque paint.net e paint são duas coisas diferentes. O mais recente é parte integrante do sistema operacional Windows. Não tenho certeza sobre o Win 10, eu uso o Win 7.