Question: As posed in the question; the statement naively seems like it should be self-evident but there are no algorithms that come immediately to mind. Suppose I have some domain $A$ (in my case a subset of $\mathbb{Z}^n$ for some $n$, but I would expect any answer to be independent of that structure), and a domain $B\subset A$. If I have an efficient algorithm for uniformly sampling from $A$, and an efficient algorithm for uniformly sampling from $B$, is there any way of 'combining' these to get an efficient algorithm for uniformly sampling $A-B$? I can certainly rejection-sample, but if $|A-B|\ll|A|$ then there's no guarantee that that will be efficient.

Answer: 
**Theorem:** For any given $A$, either there are good algorithms to sample *every* subset of $A$, or what you're describing is impossible.

**Proof** *(perhaps slightly informal)*: Suppose there are some "problematic" subsets of $A$ (those which cannot be efficiently sampled). Let $C$ be one of those subsets. From the fact that $C$ is problematic, it follows that $|C| \ll |A|$ (otherwise $C$ could be dealt with by rejection-sampling). Now let $B = A \setminus C$. Clearly, rejection-sampling *does* work on $B$, because $B$ is almost the entirety of $A$. So now we have algorithms for both $A$ and $B$, but no algorithm for $C$. Q.E.D.

Here's a ridiculous example: $A = \{(x\_1, x\_2, x\_3, x\_4) \mid x\_i \in \mathbb{Z},\; 2 < x\_i < 10^{10^{10^{1000}}}\}$ and $B$ contains only those quadruplets of numbers which are *not* counterexamples to Fermat's Last Theorem (i.e. such that $x\_1^{x\_4} + x\_2^{x\_4} \neq x\_3^{x\_4}$). It's trivially easy to sample $B$, but that gives us no clue whatsoever about how to do $A \setminus B$.
In general it is not possible to construct an efficient sampling algorithm for $A\setminus B$ given efficient ones for $A$ and $B$ (depending on your definition of efficient). Here is a simple counter-example, where efficient means $o(n)$ where $n$ is the size of $A$. Also for simplicity let $A$ be a set of integer. Now, define $B$ as $A\setminus \{x\}$ where $x$ is any integer. Then, if we have an efficient sampling algorithm for $A$ and $B$ and could create an efficient one for $A\setminus B$ which is equal to $\{x\}$, we could use it to efficiently check if $x$ is in $A$. However, by our definition of efficient this would mean that we could check membership in a without looking at all elements in a which is not possible :)