Missing Values In New Data (Before someone marks this as duplicate - I'm not asking about training data, I'm asking about new data which has come in and needs to be classified)

Suppose I've got a dataset which has 5 predictors - v1 - v5.
Since my dataset contains NA's, I've been imputing these values during training, which is fine.

However, if I get a new item to classify, it may contain 1 or more NA's. My initial thought was to create a model for each predictor variable; so for example, create a model where v2 - v5 predict v1, in the case that v1 is missing.

This would result in 5 additional models. One problem is that if v1 and v2 are missing, I'd need to guess both values somehow. I'm not sure how to do this. It makes me think that this isn't the best approach.

I'm a bit stuck, and any insight into this would be much appreciated :)
No expert here, but predicting missing value using existing variables seems suspicious to me. Does it really work?

Say $v_5$ is missing and you want to impute its value based the other variables available, using some arbitrary function $g$:
$$v_5 = g(v_1, v_2, v_3, v_4)$$
and the target variable T is:
$$T = f(v_1, v_2, v_3, v_4, v_5)$$
which is essentially
$$T = f(v_1, v_2, v_3, v_4, g(v_1, v_2, v_3, v_4))$$
or
$$T = h(v_1, v_2, v_3, v_4)$$
So essentially you are estimating $T$ using available information regardless of the missing value. Why bother to impute $v_5$ using arbitrary function?

I tend to think that imputation only makes sense only if you have a good reason for the value imputed -- often they come from domain knowledge, which means that you need to impose an external restriction on the functional and parametric form of $g$ based on your prior.