If you're going to do a black/dark/solid color outline, I highly suggest that you only outline the perimeter of the sprite, and not the inside.
Though, if the black outline can be avoided, that's even better. Especially with sprites this tiny, every pixel counts, and the outlines eat up a lot of space, that could otherwise be used for details. Also, using extra shades of colors does wonders for portraying details, too.
Here's a couple examples with different outline styles. The first is your original. The second is with extra colors, and no outlines on the inside. The third is using colors for the outlines, rather than solid colors. The fourth is just a tweak of the third one, with different colors (blues for shadows).