This is a great question.
Fisher's exact test is one of the great examples of Fisher's clever use of experimental design, together with conditioning on data (basically on tables with the observed row and marginal totals) and his ingenuity at finding probability distributions (though this isn't the best example, for a better example see here). The use of computers to calculate "exact" p-values has definitely helped to obtain accurate answers.
However, it is hard to justify the assumptions of Fisher's exact test in practice. Because the so called "exact" comes from the fact that in the "tea tasting experiement" or in the 2x2 contingency tables case, the row total and column total, that is, the marginal totals are fixed by design. This assumption is rarely justified in practice. For nice references see here.
The name "exact" leads one into believing that the p-values given by this test are exact, which again in most of the cases is unfortunately not correct because of these reasons
- If the marginals are not fixed by design (which happens almost every time in practice), the p-values will be conservative.
- Since the test uses a discrete probability distribution (specifically, Hyper-geometric distribution), for certain cutoffs it is impossible to calculate the "exact null probabilities", that is, p-value.
In most of the practical cases, using a likelihood ratio test or Chi-square test should not give very different answers (p-value) from a Fisher's exact test. Yes, when the marginals are fixed, Fisher's exact test is a better choice, but this will happen rarely. Therefore, using Chi-square test of likelihood ratio test is always recommended for consistency checks.
Similar ideas apply when the Fisher's exact test is generalized to any table, which basically equivalent to calculating Multivariate Hypergeometric proabilities. Therefore one must always try to calculate Chi-square and likelihood ratio distribution based p-values, in addition to "exact" p-values.