Handling many missing values
There are a number of different ways to impute data when you have missing values. Far to many people just delete those records, which often contain useful training data.  Further, some people advocate for simple methods like using the mean of the feature when it is missing.  I don't like this method as it seems too simplistic.

Here is a good presentation detailing a couple of methods and particularly drawing attention to imputation through maximum likelihood.

However, my favorite method is collaborative filtering, which is detailed in this paper. The nice thing about collaborative filtering is that it is easy to write from scratch and is also very popular, so is usually contained in most machine learning libraries.

Also think about taking a look at the imputation techniques that might be available in the specific machine learning library that you may be using.

Finally, a word of caution... imputing data adds some linear dependence, so you should expect that you might have to increase your regularization slightly in order to avoid high variance scenarios. I would experiment with (cross validate) removing features, removing records, then imputing data using collaborative filtering and see what produces the best results.

Hope this helps!