When can be used the "uncompute garbage" trick in quantum computing?
I think I finally figured out what the answer was :) It seems that the "uncomputation trick" was first used for quantum computing in this paper: Strengths and Weaknesses of Quantum Computing (proof of Theorem 4.14). So basically I was right when I said that it only works for "exact" computation (i.e. the output register that contains $f(x)$ is not in superposition) but it can also be used when the error probability of the algorithm is low (in this case the uncomputation is not perfect, but the amplitude of the error term is low).

Let me explain how it works: we have a quantum algorithm $\mathcal{Q}$ that takes an input $|0\rangle |0\rangle$ and produces a state $|\phi\rangle = \sum_y \alpha_y |y\rangle |b_y\rangle$ where $y$ is the working space and $b_y \in \{0,1\}$ is the output register (the result of the computation). If the computation is "exact" then all the $b_y$ are equal to a same value $b$, i.e. the state is $\sum_y \alpha_y |y\rangle |b\rangle$. We now add an extra register in which we CNOT the result: $\sum_y \alpha_y |y\rangle |b\rangle |b\rangle$. Finally, we can apply $\mathcal{Q}^{-1}$ on the first two registers so as to obtain $|0\rangle |0\rangle |b\rangle$. The uncomputation is exact.

Assume now that there is some error probability $\varepsilon$, i.e. the probability of correctly measuring $b$ is $\sum_{y : b_y = b} |\alpha_y|^2 = 1 - \varepsilon$. Let's add the extra register to CNOT the result and denote $|\phi\rangle = \sum_y \alpha_y |y\rangle |b_y\rangle |b_y\rangle $ (in which some $b_y$ are different from $b$) and $|\phi'\rangle = \sum_y \alpha_y |y\rangle |b_y\rangle |b\rangle$. If we apply $\mathcal{Q}^{-1}$ on the first two registers of $|\phi'\rangle$ we obtain $|0\rangle |0\rangle |b\rangle$ which is what we want. Unfortunately, we only know how to compute $|\phi\rangle$ (in which the last register is a superposition of $b$ and $1-b$). However, note that $\langle \phi | \phi' \rangle = \sum_{y : b_y = b} |\alpha_y|^2 = 1-\varepsilon$. Consequently, the inner product between $\mathcal{Q}^{-1} |\phi\rangle$ and $\mathcal{Q}^{-1} |\phi'\rangle = |0\rangle |0\rangle |b\rangle$ is also $1-\varepsilon$ (inner product is preserved by unitaries), which means that the amplitude of $|0\rangle |0\rangle |b\rangle$ in $\mathcal{Q}^{-1} |\phi\rangle$ is $1 - \varepsilon$. Thus, if $\varepsilon$ is small, then $\mathcal{Q}^{-1} |\phi\rangle$ is close to the correct uncomputed state $|0\rangle |0\rangle |b\rangle$. The uncomputation is almost exact.

I think this is the underlying reasoning in Aaronson's paper when he talks about "uncompute garbage". His circuit $\mathcal{Q}^{\star}$ has a very low error probability (due to an amplification step he performed before) and thus he does not care about the error part in the uncomputation.

There is also this paper: Quantum Entanglement and the Communication Complexity of the Inner Product Function (section 3) for another detailed use of uncomputation.