Long time deviations from exponential decay in radioactivity Are there any examples of common substances whose decay is not exponential?
We're used to thinking about radioactivity in terms of half-lives. This is a concept that makes sense only for a decay that is exponential. However, there are plenty of physics articles on the subject of non exponential decay. It seems to be theoretically ubiquitous. For example:

The decay of unstable quantum states
  is an ubiquitous process in virtually
  all fields of physics and energy
  ranges, from particle and nuclear
  physics to condensed matter, or atomic
  and molecular science. The exponential
  decay, by far the most common type, is
  surrounded by deviations at short and
  long times$^{1,2}$. The short-time
  deviations have been much discussed,
  in particular in connection with the
  Zeno effect$^{3,4,5}$ and the
  anti-Zeno effect$^{6,7,8,9}$.
  Experimental observations of short$^{10,11}$
   and long$^{12}$ time deviations
  are very recent. A difficulty for the
  experimental verification of long-time
  deviations has been the weakness of
  the decaying signal$^{13}$, but also the
  measurement itself may be responsible,
  because of the suppression of the
  initial state reconstruction$^{2,14}$.
1) L. A. Khalfin, Zurn. Eksp. Teor.
  Fiz. 33, 1371 (1957), English
  translation: Sov. Phys. JETP 6 1053
  (1958).
  2) L. Fonda and G. C.
  Ghirardi, Il Nuovo Cimento 7A, 180
  (1972).

10.1103/PhysRevA.74.062102, F. Delgado, J. G. Muga, G. Garcia-Calderon
Suppression of Zeno effect for distant detectors
So are there any examples of deviations from long time decay? If not, then why not? Is the theory wrong or simply impractical? And is there a simple, intuitive explanation for why long decays should not be exponential?
 A: For very long times, a decay process starts to compete with the inverse process. For instance, right now you are bathed in an ocean of matter and antimatter neutrinos with lots of different energies. For a given beta-decaying nucleus, some fraction of these background neutrinos will have enough energy to drive the inverse decay process, transforming the "daughter" nucleus into the "parent." Thus if you start off with a population of parent nuclei, you don't necessarily end up with zero parent nuclei and all daughter nuclei, as pure exponential decay would predict; instead you end up with a tiny fraction of the parent nuclei remaining in the sample. The size of this steady-state fraction depends on the local neutrino density and energy spectrum.  You can make the same argument for other decay modes.
A: To be honest, the paper listed as reference 12 in the OP's quote (1) gives as good an answer to most of these questions as you can hope to get:

For example, taking $\omega(E)$ as a Lorentzian function for all E
  yields the well-known exponential decay at all times.
  However, in real physical systems, $\omega(E)$ must always
  have a lower limit, which is, for example, associated with
  the rest mass of scattering particles.

In other words: a system with a perfectly exponentially decaying probability of remaining in the initial state, of the form
$P(t)=e^{-t/\tau}$,
must necessarily have an energy distribution of that initial state that is exactly a Lorentzian:
$\omega(E)=\frac{1}{\sqrt{2 \pi}}\frac{2/\tau}{(1/\tau)^2+(E-E_0)^2}$
But this is a function that is nonzero on the entire interval $(-\infty,\infty)$, while any real system necessarily has a minimum energy. Using some fancier Fourier analysis (2), one can prove that this means that in the $t \rightarrow \infty$ limit, any decay must go slower than exponential, and it generally turns out to be a power law. As rob mentions, this non-exponential behavior can also be seen as the result of the inverse decay process becoming non-negligible, and that point of view is also discussed in (2).
Most of the theory and review papers on this stuff that I've seen dates back to the 50s-80s, and don't even speculate on experimental prospects. However, (1) from above claims to give the first observation (in 2006) of this power-law decay. The authors note that in searches for this behavior using radioactive decay, one must look for deviations at the level of $10^{-60}$ of the initial signal (!), so it's not surprising that no one has been successful. Instead, they use the decay of the excited state of some organic molecule instead, which is very broad compared to the resonant energy and as a result crosses into this nonexponential regime much sooner.

As a final side note, the OP doesn't ask about short time deviations from exponential decay, but it's easy to see where those come from too. Using
$P(t)=|\langle \psi_0 | e^{-i H t} | \psi_0 \rangle|^2$,
and Taylor expanding the time evolution exponential, one finds
$P(t)\approx 1-\sigma_E^2 t^2$,
where $\sigma_E$ is the energy spread that $\psi_0$ has among the states of $H$. This is a very general consideration that applies to pretty much any time evolution.
A: http://arxiv.org/abs/1304.6885  There are many papers on apparent sinusoidal modulation of overall beta-decay.  One explanation is competing pathways with different kinetics whose rates add to beats.  The obvious non-exponential decay case is electron-capture decay of a fully ionized atom.
