This answer will try and outline all the different possibilities I came across over the last couple of years, including drawbacks. But first, let me outline the problem a little.
To appreciate the problem, a first simplistic starting point is here.
What the authors observe is similar to what you observed. "Optimization is Error-Maximization" is an often cited quote.
Why is that?
To build some intuition, look at the unconstrained solution of the MV problem. It is proportional to the inverse of the variance Covariance matrix $\Sigma^{-1}$. You see that by setting the first derivative to zero and solving for the weights.
The role of the spectrum of $\Sigma$
If you look at the Eigenvalues of $\Sigma$, the problem occurs when they are close to $0$. That is, because the inverse $\Sigma^{-1}$ has the inverse eigenvalues, which in turn means that upon solving the problems, certain directions are being extremely magnified. Also, these directions are very unstable, meaning that upon updating $\Sigma$ at a later point in time, directions and thus your solution are likely to show big changes over time and the solution is unstable.
==REMEDIES==
Be aware that all of the following methods will cause a loss of information of some kind. Also, I do not prefer one method over the other.
1. Messing around with the spectrum
One of the more straightforward things: If an Eigenvalue is, say $<10^{-6}$, set it to $10^{-6}$ and recalculate the variance covariance matrix.
(If $\Sigma = E^{T} \Lambda E$ with Eigenbasis $E$ and spectrum $\Lambda$, you can define $\hat{\lambda}_i = \text{max}(10^{-6},\lambda_i)$ and then calculate $\hat{\Sigma} = E^{T} \hat{\Lambda} E$.
(Hint: you can force total variance to be the same by rescaling but the difference shouldnt be big).
Bear in mind that there are numerous ways you could do this but this is the most straightforward one I think.
More difficult is the question how small do you accept your eigenvalues to be...
2. Factor Models
If we can express $N$ asset classes in terms of $F$ factors, this is effectively a dimension reduction. If you drop the idiosyncratic parts and the variance covariance matrix of the factors is stable (usually, the idea of factors is that their correlation is not too high). You would need to reformulate your problem
3. Shrinkage Estimation
In numerics, there is the common trick to "add a diagonal"($\hat{\Sigma} = \Sigma + \lambda \mathbb{1})$ to get the spectrum away from $0$. Now, if we come from statistics the total error of an estimator can be decomposed in a bias plus a variance component. The idea is to reduce the estimation error further by taking a bias (you can actually use an ansatz like metioned above and calculate the $\lambda$ if I remember correctly). Look at Shrinkage Estimation.
4. Expected Return estimation - Black Litterman method
One finding from employing the BL-method is that the results are more stable. This is because the expected (prior) returns are calculated via the market weights $w_M$ and the variance-covariance matrix: $\mu \approx \Sigma w_M$. Also, you can see that via the very heuristic argument that if your solution $w \approx \Sigma^{-1} \mu$ and $\mu \approx \Sigma w_m$ then this will be stable, as the idea is that both in a way "cancel out". I know this is by no means mathematically correct but just to give you a feeling.
I am sure the list is by no means complete. Take also a look at robust optimization. I didnt cover this here.
