Alpha testing is always going to give you funky, aliased results when you undersample the texture map. Mipmapping just plain doesn't work, because you can't pre-filter the results of the comparison and subsequent depth testing/rasterization. Basically what you end up with is AlphaTest(Filter(TextureAlpha)) when what you really want is Filter(AlphaTest(TextureAlpha)) instead (FYI, this is almost the exact same problem that you have with filtering shadow maps). Performing texture filtering and mipmapping on the the alpha value will give you a smoothed alpha value in the shader, but it won't actually accurately represent the shape you're trying to represent. This can get really bad in the lower mip levels, where the averaging of neighboring alpha values can end up causing features to essentially "disappear". You can alleviate the problem somewhat by increasing your sampling rate, which requires enabling MSAA, taking multiple samples from your alpha texture, and then using the alpha test results for each sample to generate an output coverage mask.
A common, much cheaper method to work around this issue is to change the way you generate mipmaps for the alpha channel such that you end up with something that's a better representation of the overall coverage of the shape that you're trying to represent. This article explains a simple way to do that. It's not always a silver-bullet solution, but it can certainly help in a lot of cases.