Check your graphic software documentation. Most of them have ability to make sharp edges (single color transparency) but it is not used by default.
And even latest version of MS Paint makes smoth edges by aplying Anti-Aliasing effect to the imgaes. But it is quite terible at it. Whatever you do don't save your image until it is finished as MS Paint aplies this Anti-Aliasing efect every time before image gets saved. So parts of image that existed for several saves literaly become blurred becouse of this.
Last time I was doing some graphics in MS Paint I use the one that comes with Windows 98 but since it doesn't support PNG images as new ones does I had to reopen and resave the images with new one to make transparancy work. But yeah I ended up with that strange colored line around my objects.
That and the fact that I don't have any proper graphic making program encouraged me to try and make one myself. Unfortunately it stil isn't done like most of my stuff. But it will be some day.