Further reading shows that http://en.wikipedia.org/wiki/Sparse_approximation is supposed to be NP-hard, so it can't be that the L1-norm minimum produces the "L0-norm" minimum every time.

Yes, but if I understand correctly it occurs with probability 1 for many classes of probability distributions (including this one, I think).

http://statweb.stanford.edu/~donoho/Reports/2004/l1l0approx.pdf which is given as the Wikipedia reference for L1 producing L0 under certain conditions, only talks about near-solutions, not exact solutions.

It says that if the L0-pseudonorm solution has an error epsilon, then the L1-norm solution has error up to C*epsilon, for some positive C. In the exact case, epsilon is zero, hence the two solutions are equivalent.

Also Jacob originally specified that the coefficients were drawn from a Gaussian and nobody seems to be using that fact.

You don't really need the fact for the exact case. In the inexact case, you can use it in the form of an additional L2-norm regularization.