A bound system will indeed have a lower mass than it's constituent free parts. The binding energy is usually understood to be the energy it would take to separate the bound system to free constituent parts. Then we would say $M_{tot} = M_1 + M_2 - E_{bind}/c^2$ Or we could by convention make the binding energy a negative number and say it "increases" mass by a negative amount. I think people speaking a little loosely is what's causing the confusion.
If we are talking about a nucleus, then it is impossible because of color confinement to separate the constituent parts (quarks) to independent free particles, so what we call the "binding energy" in this case is not as clear.
When people say that the decay rate depends critically on the $Q$ value, they're talking about alpha decays compared to other alpha decays. When you compare alpha decay to emission of other small clusters, the dependence on the atomic number $Z_c$ of the emitted cluster is much more prominent. The reason is as follows.
In the Gamow model of beta decay, we assume that the decay rate is the product of three factors: (1) a hand-wavy probability of preformation of the cluster; (2) the frequency with which a cluster assaults the Coulomb barrier; and (3) the probability of transmission through the barrier. (Re #1, don't take Ohanian too seriously when he says this factor is 0.1 to 1. Actually the literal existence of any cluster bouncing around inside an atomic nucleus would violate the exclusion principle. The whole thing is just a model.)
The critical factor is the tunneling probability $P$, which can be estimated using the WKB approximation, which looks like $\exp(-\int\ldots)$, where the integral is over the classically forbidden region. The integral depends on the Q value, because a higher Q value both shrinks the classically forbidden region and reduces the value of the integrand within that region. However, the height of the Coulomb barrier is proportional to the product $Z_cZ_d$ of the atomic numbers of the cluster and the daughter nucleus. If you want all the gory details, you can google the Geiger-Nuttall equation. But the result turns out to be of the form $\ln P=a-b$, where the $Z$-dependence is dominated by the term $a=(1/\hbar)\sqrt{32Z_cZ_d m_c R ke^2}$. For the alpha decay of uranium, we have $a\approx 74$. In Yval's example, decay by emission of 9Be basically doubles the value of $a$, which reduces the decay rate by a factor of $e^{-74}\approx10^{-32}$.
In the question, Yuval estimated that emission of Be should only be down by a factor of $e^{-2}$ relative to emission of alphas. This was an algebra mistake. We have an expression of the form $e^{-Zu}$, where $u$ is a constant. Changing this expression from $e^{-2u}$ to $e^{-4u}$ doesn't just reduce its value by a factor of $e^{-2}$, it reduces it by $e^{-2u}$, which is a huge factor.
Actually, as pointed out by JoeHobbit, the real mystery isn't why we don't emit larger clusters, it's why we don't emit lighter objects like protons or deuterons. A proton doesn't have to worry about preformation, and its tunneling probability would be much higher. Possibly this is due to the lower $Q$ value for proton emission. This comes into the Geiger-Nuttall equation because $b\propto Z_cZ_d/\sqrt{Q}$. In fact proton emission does occur, but it's only competitive for extremely proton-rich nuclei. There is also neutron emission, which doesn't involve any Coulomb barrier at all; as you'd expect, its half-life is very short (on the order of the assault frequency) when it's energetically allowed.
Best Answer
I always get confused when I try to use binding energies directly, partly because of the sign issue, and partly because differences in binding energies show up in the third or fourth significant figure. My favorite reference instead lists for each isotope a "mass excess," which is the difference (in energy units) between an observed mass and the naïve mass of $A$ atomic mass units. For beryllium and helium we have \begin{align} \rm\Delta({}^8Be) &= \rm 4.9416\,MeV \\ \rm\Delta({}^4He) &= \rm 2.4249\,MeV \\ 2\cdot\rm\Delta({}^4He) &= \rm 4.8498\,MeV \end{align} This makes it clear that a $^8\rm Be$ is heavier than two $^4\rm He$ by about $0.1\,\rm MeV$ — it has more excess mass.
So what was wrong with your binding energy approach? You have \begin{align} \rm BE({}^8Be) &= 56.49955\,\rm MeV \\ \rm BE({}^4He) &= 28.3\rm\,MeV &\text{(careful with precision here)}\\ 2\cdot\rm BE({}^4He) &= 56.6\rm\,MeV \end{align} Here you have the same energy difference, about $0.1\rm\,MeV$, but it appears to go the other way, as you point out in your question. That's because helium is more tightly bound than beryllium; when beryllium-8 fissions, the extra binding energy is released.