How can we have multiple "exact" tests? Looking over the differences between Fisher's exact test and Barnard's test, it seems I'm missing something fundamental. If both are exact tests, shouldn't both give the exact and identical value for $P(data | H_0)$, in this case $P(data | p_{r1} = p_{r2})$?

Not really; all an exact test needs to do is accept or reject the null hypothesis based on the actual distribution of the test statistic.  Consider the following two tests of whether the mean of a Normal distribution with known standard deviation equals zero.

*

*A z-test for whether the mean $= 0$.  No explanation needed!


*A binomial test for whether the mean (= the median) $= 0$.  Here we assume the probability of an observation being above the median $= 0.5$; this is an exact test, as the binomial distribution with probability $0.5$ is the true distribution of the number of observations above the median.
These two tests will (almost) certainly give different results when calculating the probability of the observed data under the null hypothesis, but they are both exact.
Expanding on this example to address a comment:
The key here is that, although the underlying distribution is the same in both cases, the test statistics $T_N(x)$ and $T_B(x)$ are not (regardless of whether the null hypothesis is true.)  There is no 1-1 map between the two (this is important.)  Consequently, $p(x|T_N(x))$ and $p(x|T_B(x))$ aren't guaranteed to be the same either.  The underlying distributions are the same; the distributions conditional upon the test statistic are not.
However, conditional upon the test results failing to reject the null hypothesis, in both cases we have the "estimated" mean $= 0$ and standard deviation $= 1$.  Consequently, $p(x|H_0, T_N(x)) = p(x|H_0, T_B(x))$; the test statistic is irrelevant as the distribution is fully determined (in this case) by $H_0$.  In the more general case where we have parameters $\theta$ that are not specified by the hypotheses and therefore need to be estimated, as long as a) the estimation procedure is the same regardless of the test chosen, and b) neither test rejects the null hypothesis, we have $p(x|H_0, \hat{\theta}, T_1(x)) = p(x|H_0, \hat{\theta}, T_2(x)) = p(x|H_0, \hat{\theta})$.
