The problem in your example is that the grey anti-aliased pixels are closer in brightness to the blue than it is to the black. So what about offering the user the chance to increase the size of selected regions? Increase the various black selected zone by half a pixel and all your problems will disappear.
Tim
Tim