What can we say about operators in Lp that commute with translation? Suppose I have an operator $T: L^p(\mathbb{R}^d) \rightarrow L^r(\mathbb{R}^d)$ that commutes with translation: $\tau_h \circ T = T \circ \tau_h$. Can I conclude that $T$ is a convolution? If not, is there anything else I can say?
For $L^1$ and $L^2$ the question is settled, and the answers are given in this question: Bounded linear operators that commute with translation. Both answers use machinery specific to $p=1$ and $p=2$.
For general $L^p$ my approach was to define a linear functional
$$
 \phi(f) = (Tf)(0);
$$
and then use the fact that $(L^p)^*=L^q$ to get
$$
 \phi(f) = \int_{\mathbb{R}^d} f g dx.
$$Because
$$
  (Tf)(x) = \tau_{-x}((Tf)(0))= T(\tau_{-x}f)(0)
 = \phi(\tau_{-x}f) 
$$
we get 
$$
  (Tf)(x) =  \int\tau_{-x}f(y)g(y)dy = \int f(x+y) g(y)dy=  (f * g)(x)
$$
(There's a sign problem here, but that can be fixed by modifying $\phi$.)
The problem with this approach is that $\phi$ is not necessarily continuous because point evaluation is not continuous in $L^p$. However $T$ is translation invariant, which gives us something. For instance, we can prove that, given any sequence $f_n$ converging to $f$ in $L^p$,
$$
  \phi(\tau_xf_n) \rightarrow \phi(\tau_x f)
$$
for almost all $x$ in $\mathbb{R}^d$. (To prove this use the fact that
$$
  \lim_{n\rightarrow \infty} m( \{ |(Tf_n)(x) - (Tf)(x)| > \epsilon \} ) = 0.)
$$
Can it be made to work? If $T$ is translation invariant is $\phi$ continuous?
 A: What you want to show is (more or less) true.
Theorem 2.5.2 in Grafakos' book "Classical Fourier analysis" implies under your assumptions that $Tf = f \ast \nu$ for all Schwartz functions $f$ and some tempered distribution $\nu$.
The proof is essentially as you indicate, but the problem is that $(Tf)(0)$ makes no sense in general, because $Tf$ is only an $L^r$ "function" (more precisely, an equivalence class of a.e. equal functions).
But for $f \in \mathcal{S}$, one can show that $\partial^\alpha (Tf) = T(\partial^\alpha f)$ (where the derivative is understood in the sense of (tempered) distributions).
This implies $\partial^\alpha (Tf) \in L^r$ for all $\alpha$, so that a (very weak) form of a Sobolev embedding theorem shows that $Tf$ is actually continuous (has a continuous representative), so that for $f \in \mathcal{S}$, the expression $(Tf)(0)$ is well-defined. The proof also yields that $f \mapsto (Tf)(0)$ is a tempered distribution. This is then used to construct $\nu$.
In general, the question is, what you mean by "a convolution". In the sense above, the result is true on the space of Schwartz functions for a suitable form of convolution (tempered distributions).
If you want to conclude that the convolution is against an $L^1$ function (or something similar), this is in general not true, not even for $L^2$, because we can take $m = \chi_{(-1,1)}$ for example and define $Tf = \mathcal{F}^{-1}(m \cdot \widehat{f})$. Then $Tf = f \ast \mathcal{F}^{-1}m$ and $\mathcal{F}^{-1}m \notin L^1$ (because otherwise, $\chi_{(-1,1)} = \mathcal{F}\mathcal{F}^{-1}m$ would be continuous by Fourier inversion).
Concerning the Fourier transform as a map $\mathcal{F} : L^p \to L^{p'}$, this is only true for $1\leq p \leq 2$ (this is called the Hausdorff Young inequality), see http://en.wikipedia.org/wiki/Fourier_transform#On_Lp_spaces, more precisely

In fact, it can be shown that there are functions in $L^p$ with $p > 2$ so that the Fourier transform is not defined as a function (Stein & Weiss 1971).

