Stothers' thesis, from 2010, p. 18, lists 19 and 23 as the current lower and upper bounds. These are the same numbers that I have heard from some researchers in the field, and I don't think there has been any improvement since then.

Why is it a difficult problem? Simply because it is high-dimensional, non-convex optimization problem, with lots of local minima. To specify a rank-19 9x9x9 tensor, for instance, you need about ~~19x9x9x9~~ 19x(9+9+9) entries (slightly less since you can normalize some things, actually), so that's the kind of dimensionality you are dealing with. Computers still can't deal reliably with this number of degrees of freedom for a problem like this. Even testing all possible decompositions with entries in $\{-1,0,1\}$ is not feasible.

Another difficulty for killing the problem numerically is that solutions can be "at infinity": for instance, let $T_\epsilon$ be the tensor such that
$$
T(:,:,1)=\begin{bmatrix}1 & 0\\ 0 & 1 \end{bmatrix}, T(:,:,2)=\begin{bmatrix}0 & 1 \\ 0 & \epsilon \end{bmatrix}.
$$

$T_0$ has rank $3$, but any $T_\epsilon$ with $\epsilon \neq 0$ has rank 2. The decomposition can be parametrized explicitly and contains some $\epsilon^{-1}$ entries. So if you run an optimization algorithm to find a rank-2 decomposition of $T_0$, the residual will converge to 0, but at the same time the single entries of the decomposition will diverge.
In geometrical terms, the sets $S_\ell = \{T: \operatorname{rank} T \leq \ell \}$ are not closed, unlike in the matrix case.

EDIT: fixed error in number of degrees of freedom; see Luke Oeding's answer.