Literally, Fisher's exact test requires you to count all of the possible tables with the marginal totals you have. You then compute the proportion that are as extreme or more extreme than your observed dataset. That proportion is the p-value. If your $N$ is moderately high, it becomes too onerous to form and count all the possible permutations. However, simulating will give you an empirical estimate of the proportion that is very good. So at a certain point, simulating is a more convenient option. That is, this isn't really about the assumptions.
On the other hand, your belief that you have to use Fisher's test when you have small cell counts is common, but incorrect. For more on that, see: Alternatives for chi-squared test for independence for tables more than 2 x 2.