It seems that shrinking the covariance matrix is especially useful if the number of individual stocks is greater than the number of data points. However is there any special gain if you're not constrained by the data ?
When using the estimated covariance in the context of mean-variance optimization, then, yes, shrinking the covariance matrix is useful even when you have sufficient data.
A good reference is Golts and Jones, A Sharper Angle on Optimization, who discuss convariance shrinkage among other techniques and give two examples of the usefulness of shrunk covariance estimates in forming (unconstrained) optimal portfolios. The first is desensitizing the optimizer to small variations in alphas of highly correlated assets. The second is controlling leverage.
There's more than one way to shrink a covariance matrix. You can think of shrinking a covariance matrix as part of general class of estimators that limit the norms of a matrix. You could alternately think of shrinkage as a form of Bayesian analysis. Given the broad set of techniques one could use, it can be more helpful to think in terms of techniques to reduce estimation risk.
For instance, suppose you simulate some data (really you want to simulate a mean and covariance with error and then simulate data using those parameters) and then apply techniques that reduce the impact of estimation error while constructing an efficient frontier. If you do this many times, you will find that the techniques that reduce the estimation error will be closer to what the frontier would look like if you knew the true mean and covariance than if you used the sample parameters. So to this extent, techniques do reduce estimation error would be a good thing.
In practice, the techniques lead to more diversified (less concentrated) portfolios and increase stability over time, which tends to reduce turnover. It's not necessarily clear that the techniques would lead to better returns, however.