Textbook RSA with $e=3$ and short random message

This is a simplified version of a question I made long ago, that never got an accepted answer.

It's given $$N$$ of $$n=2048$$ bit, assumed hard to factor, which two prime factors each are $$\equiv2\pmod3$$, so that the public exponent $$e=3$$ is usable. It's also given $$C\in[0,N)$$, known to have been obtained as $$C=M^3\bmod N$$ for random $$M$$ of exactly $$m$$ bits, that is $$M\in[2^{m-1},2^m)$$, for some public parameter $$m$$.

Up to what $$m$$ can we realistically find $$M$$, in say a day on a standard PC?

Here are the attacks I see so far:

1. If $$m<\lfloor n/3\rfloor$$ that is $$m<682$$, it holds $$M^3 thus $$M=\sqrt[3]C$$, which can be readily computed.
2. For very slightly larger $$m$$, it holds $$M=\sqrt[3]{x\,N+C}$$ for small $$x\in\mathbb N$$ and we can enumerate $$x$$ and test $$x\,N+C$$ until one is a cube. For $$m=n/3+k$$ the effort grows as $$\mathcal O(8^k)$$, thus this can't extend the range for $$m$$ much.
3. As an improvement of 2, it's possible to skip many $$x$$ in the search by observing that when $$u\equiv1\pmod 6$$ is prime, then $$x\,N+C\bmod u$$ is among a set of only $$(u+2)/3$$ values: $$\{0,1,6\}$$ for $$u=7\,$$, $$\,\{0,1,5,8,12\}$$ for $$u=13\,$$, $$\,\{0,1,7,8,11,12,18\}$$ for $$u=19\,$$, $$\,\{0,1,2,4,8,15,16,23,27,29,30\}$$ for $$u=31$$. Doing this for $$u\le61$$ reduces by a factor over $$1099$$ the number of candidates $$x$$, and we can make a "wheel" of $$4729725$$ increments of $$x$$ to quickly go from one $$x$$ to the next. Larger primes $$u$$ can be used to quickly weed out most of the remaining candidates $$x$$, and I think a standard PC can eliminate like $$2^{48}$$ candidates $$x$$ per day; thus we can tackle like $$m\approx n/3+16$$.
4. On top of improvements 2 and 3, we can hope that $$M$$ is divisible by a small integer $$v>1$$: there's probability >73% that holds for at least one $$v\in\{2,3,5\}$$. If so $$\hat M=M/v$$ is an integer, and $$\hat C=v^{-3}C\bmod N$$ that we can compute is such that $$\hat C={\hat M}^3\bmod N$$. We can thus carry the attack of 1/2/3 on $$\hat C$$, and if we find $$\hat M$$ go back to $$M$$.

I don't see that 3 and 4 combined can work with sizable probability for $$m>n/3+20$$ or so. But perhaps there is a smarter attack, e.g. with the LLL?