Solutions of the equation $x^x=\frac{1}{256}$

The problem is here:

the function $x^x$ doesn't exist for $x < 0$

This is wrong. Or, if you take it this way, then $x = -4$ cannot be and is not a solution, for then $(-4)^{-4}$ would have to be undefined as well.

You see, whenever you talk about functions, you cannot forget the domain - and in this case, the domain of $x \mapsto x^x$ for $x$ real is a bit tricky, and your question solution lies right in the tricky part. Everyone can agree that $(0, \infty)$ is part of it, but not everyone necessarily agrees on what the case is for other values of $x$. When you say

one can check by substitution [that it is indeed a solution]

you are presuming a larger domain than the one you just gave in order to do that "substitution", and that changes the answer to the question, and indeed it changes results like "that there is no solutions below $x = \frac{1}{e}$".

Now Wolfram does, indeed, presume a larger domain. In fact, it takes the domain to be all of $\mathbb{R}$, and moreover takes the codomain to be $\mathbb{C}$, so you are right that complex numbers play a role here.

Even more in fact, given that the domain is part of the definition of the function, you could say you and Wolfram are working with two different functions, that both happen to be denoted by the ambiguous notation $x^x$. Hence there is no surprise that there will be two different answers as to what the solution set is.