Grazie a questo post: Paint.NET v1.1 "Beta 2" Download, ho finalmente deciso di provarlo... e che posso dire complimenti!
Funziona solo con Windows XP SP1 o superiori, ed è completamente scritto in C#. Richiede naturalmente il .Net Fx 1.1
Non vedo l'ora che venga rilasciata la versione finale, non tanto per i problemi (finora non ne ho trovati), quanto per la possibilità di avere anche i sorgenti, rilasciati con una versione modificata della licenza MIT.
Per i pigri che non hanno nemmeno voglia di cliccare il link, vi riporto la schermata. Cliccandola non verrà fuori il numero di telefono di Eiko (la signorina giapponese...) ma la pagina ufficiale del programma 
:
Per gli impazienti, i sorgenti della versione 1.0 potete trovarli qui.