There's a new Paint.net version out -- I don't use it, but I know it has lots & lots of fans.
If you haven't tried it, install is higher impact -- you'll likely never get rid of everything IMHO. All told the registry gets ~2k new entries, C:|Windows\ WinSxS gets roughly a couple dozen files, plus there are additions/changes to .NET, though Paint.Net itself only adds 2 folders: the program folder [90 files, 15 folders, ~30 MB], and a folder under User Local App/Application Data.