Here is the number alignments of five 31bp reads reported by 5 aligners:
Sequence bwa -R10000/GEM -s1 MrFast -e2 bowtie -l31 bowtie2 -------------------------------------------------------------------------------------------------------- AGGGCCAGCTAAATTTTGTATTTTTAGAAGA 27 2-mismatch 21 2m 27 2m 1 2m; 1 3m GTCAGTATGGCCAATTTCACGATAATGATTC 50 2-mismatch 30 2m 50 2m unmapped TTTGATTCTTCTGTCTTTTCTTCTTTAATAG 103 1m; 4119 2m 60 1m; 2053 2m 103 1m; 4098 2m 103 1m; 24 2m GCCCCCTGAGCAGCTGGGATTACAGGCGAGC 10 1m; 121 2m 10 1m; 115 2m 10 1m; 73 2m 10 1m; 7 2m; 17 3m ATCTTTCTCTTCTTATTTTTGTATGAATATA 10 1-del 10 1d unmapped 10 1d
Only BWA and GEM report all the hits up to 2 mismatches/indels. Bowtie1 finds the best hits, but not gapped hits or suboptimal hits. Bowtie2 and MrFast may miss 2-mismatch hits. On chr1, segemehl does not output suboptimal hits. It finds all the 1-difference hits but misses two 2-mismatch hits. I have not tried segemehl on whole-genome as it is inconvenient to run.
I have also tried bwa, bowtie and gem at a larger scale. For ~4200 31bp reads having 2 mismatches, bwa and gem report exactly the same number of hits for every read. Bowtie on the other hand misses hits for 25% of reads - bowtie does not guarantee to find all hits. <del>If I use bwa and gem to find 2-difference hits, bwa finds more, suggesting that gem does not guarantee to find all gapped alignments.</del> Note that I am not saying that bwa can find all 2-difference hits. In theory it should, but in practice, optimization to the original algorithm may lead to bugs in corner cases, which I have never checked.
In summary, among the mappers tested here, bowtie, bowtie2, mrfast and segemehl do not guarantee to find all the 2-mismatch hits for ~30bp reads. Only bwa and gem achieve full-sensitivity to mismatches. <del>Bwa is more sensitive than gem to gapped alignments.</del> Nonetheless, at the full sensitivity, gem works with 100bp reads, but bwa has to use heuristics. Gem is a better mapper than bwa (IMHO gem is the first mapper better than the origianl bwa all around), as long as you use it the right way.
EDIT: for gapped alignment, bwa may produce duplicated hits (a bug I thought I have fixed...). That said, gem does not guarantee to find all gapped hits. I have found one example with the best match contains 1 gap, while gem only reports 2-mismatch hits.
EDIT2: Conclusions (so far):
With the suggestions from nkrumm and David, we can say that bwa, gem, mrfast, segemehl and RazerS3 probably guarantee to find hits within certain hamming distance threshold. These mappers all support gapped alignment, but whether they guarantee to find all gapped hits given an edit-distance threshold has not been concluded. Neither bowtie nor bowtie2 guarantees to find all hits.
For practical uses, bwa's try-and-reject strategy is probably faster for <32bp sequences. MrFast, gem and razers3 all use the pigeon hole approach. They should be faster for longer reads (e.g. 36-100bp). BWA and gem index the genome. They have fixed memory footprint and is easier to run (you do not need to split the read file when it is too large), and also run much faster if you only have a few to a couple of thousands of reads at hand. I would recommend them in general.
All that being said, for 100bp reads, finding all hits given a certain edit-distance threshold is not sufficient. We would like to see if alignments containing one reasonably long gap (say 7bp insertion) and to rank the hits by affine gap penalty instead of by edit distance. In computer science, edit distance is popular as it is clearly defined and many efficient algorithm exist to find matches. However, affine gap penalty is of more biological/evolutionary meaning.