Labelling a missing value as -1000 (assuming a non-missing value is much smaller in absolute value) will not cause problems with anything based on decision trees/stumps (bagged/boosted). You might also have some success with mixture models, for example a GMM - the learning algorithm will allocate some components to cover the missing data. Same for non-parametric density estimators, nearest neighbours, or SVM with RBF kernels.
Note that in all these cases, even if the model works, there will be a waste of resources ("model space budget") if feature #25 is always present in your testing data. In other words, your model will have learnt how to deal with tricky examples that will never occur when classifying new data! But if feature #25 will sometimes be missing in some of the data you will encounter "in the field", this is the way to go.
Do not expect things to work with algorithms such as neural networks or support vector machines with linear or low order polynomial kernels.
If feature #25 will never be missing "in the field", it might be simpler to just extrapolate feature 25 in your training data. To do so, you can proceed as follows:
Option 1: Nearest neighbor
- Normalize all features (except #25).
- For each training example in which feature #25 is missing, search for the nearest training sample, according to features (1 .. 24 and 26 .. 36), for which feature #25 is present.
- Assign to feature #25 the value taken from the nearest neighbour.
Works best when you have lots of data (but not too much so as to make the search feasible) with kinky distributions.
Option 2: Regression
Use any regression method of your choice to find a relation ship between feature #25 and the other features, on the subset of your dataset in which feature #25 is not missing. For example, a linear regression.
Use the result to predict feature #25 on the remaining training instances.
Works best when your features are "well behaved" for the regression method you plan to use (for example, see the prerequisites for linear regression).