Your question seems rather broad and you could specify this more if you need more specific answers. Here are some general observations:

The noiseless case, i.e. $\epsilon = 0$:
The condition on $X$ is that the pairs $(X_i, Y_{\pi(i)})$ lie on a single hyperplane for some permutation $\pi$ of $1,\ldots, n$. In dimension 1 this is easy to check, just sort the $X$ and the $Y$. Since you can sort ascending or descending, there is no unique solution unless $\beta$ is zero. In higher dimensions a straightforward attack would be to check linear dependence of the pairs for each possible permutation. Of course this gets cumbersome in practice if $n$ is larger than 9 or 10. Hence an important factor in assessing "efficiency" of the solution is the size of $n$ and the number of factors $p$.

The case with noise:
I think here you really need to specify what you want from a solution and what your criterion for efficiency is. Each permutation of the $Y$ is a standard least squares problem and after solving those you will have (in general) $n!$ different solutions for $\beta$. Depending on your estimation problem, you might want to choose the average of those, or that value of $\beta$ which gives you the lowest estimated $R^2$ or variance of $\epsilon$ or something else entirely. From what you say I do not see a single clear criterion for an estimate of $\beta$.

Anyway, due to the permutations involved, I guess the problem will become quickly harder for growing numbers of $n$.

Normally one does regression either for explanation or prediction. Both seem to be difficult concepts in your setting. Do you mind, explaining why you are interested in this?