It just depends on whether the image is staying on a fixed background (or backgrounds with similar values) or on top of different objects (detailed backgrounds, other sprites, tiles etc, with various colors).
If it is the first one, AAing the outside part of the outlines will make it smooth and will work just fine.
If it is the later, unless you use alpha transparency there is no universal AA that works on everything, so you will be seeing random pixels over the things the AA doesn't work on.