Is excluding cases with missing data fine for a predictive (not explanatory/descriptive) model? Suppose I have some observations $(x_i,y_i)$ from some population—y is binary and x is a real number or vector of real numbers.
x    y
1    1
1    0
nan  1
nan  0
...
4    1

I would like to build a model to predict $y|x$
Assume all cases have $y$ and that I remove all, for example, 50% of the cases that have missing $x$.
We then have a predictive model $m$ for $y|\{x, \text{$x$ not missing}\}$. This could be extremely useful.  For example, suppose that we are trying to predict some disease; any time someone presents with $x$ not missing, we can use our model.  It's too bad that we cannot say anything for those with $x$ missing, but we have generally improved the world for the subpopulation for which $x$ is collected.
If, however, we remove cases with missing $x$, and we then (1) decide to use $m$ on cases with $x$ missing or (2) make some statement about the whole population based on our estimated coefficient, this is clearly not correct. For (1), we would be using the model on a population different than the one for which it was trained.  For (2), we would be ignoring the bias we might have introduced by removing cases with missing $x$.  
I think it is for the second reason especially that removing missing data gets a bad rap.  However, using $m$ as originally described if you are honest about the model not applying to cases with missing x seems to be a good idea (although not the $best$ idea, which would be to impute and have $m'$ for the whole population), and not to be kind of incorrect like (1) or (2). In this way, removing missing data does not introduce 'bias' it introduces constraints on the usability of the model?
 A: It Depends
Whether excluding cases with missing data is fine or not depends on a few factors. Whatever choice is made requires justification, so there is a bit or work to do with the data. The more ancillary information available to you, the better you can make a choice. Testing the randomness of the missing values is essential to guide your steps. This is because things become much more complex once you start to look at biased missingness. 
I'll use an example of an arbitrary disease that requires some blood test and a questionaire. 
Are values 
Missing Completely At Random (MCAR): no pattern at all to the missingness. This may be that one subject is missing because the person got caught in traffic and didn't have time to complete all the tests, another because they faint at the sight of needles, another because the doctor's scrawl was completely uninterpretable. The reasons are unnconnected to each other and to whether the person has the disease or not.
Missing At Random (MAR). Has a relationship with what you have observed, but is not due to the underlying value. For example a questionnaire answer may be more likely to be missing in old subjects who have worse memory, but the likelihood of forgetting is not related what the answer would have been. Age may be a risk factor in the disease, so the forgetting is confounded with disease risk even through it is not caused by the disease.
Missing Not At Random (MNAR) there is a pattern to which variables are missing, the likelihood of being missing is biased by the actual value of the variable. For example, males may not wish to report impotence and choose to not report it. To diagnose this often needs additional data as you don’t know what the value should be. 
See
https://www.theanalysisfactor.com/missing-data-mechanism/ which explains these and provides some advice on how to deal with the different types.

Possible Solutions
The five options I am aware off (1st 2 you have already discussed) are:


*

*Ignore missing data in model. When you come to predict new
samples that have missing data it will return and invalid result due
to the missing value. You are right that this approach will limit
your ability to make generalisations about the entire population unless you can prove that the missing data is MCAR. The model will fail when missing data is present, so you are not going to produce false predictions. Failure is useful information and not to be ignored. Mechanisms to
handle the failure need to be appropriately designed. This will have theoretically have a neglible effect if data is truely MCAR as the missingness is unbiased. With MNAR there is definite bias in the missingness and this would be passed onto the model that ignores missingness. With MAR there is a risk that although the missingness is not due to the disease, it may be linked to factors that are confounded with disease and so may still bias your model. 

*Impute missing data into model. As a couple of commenters have pointed out the main value of imputation is maintaining statistical robustness of the dataset. It doesn't help the individual receiving a diagnosis if you replace their true value with (for a simple case) the mean of the population. Its aim is to preserve the overall statistical properties of the dataset for the general population. Imputation works best in a multivariate
dataset where the relationship with other variables can help improve
the imputation (specific patterns in variables T, U, V, W may be
associated with more probable values of X) as these allow tailored estmation of the individual's value. If mechanisms causing
missingness (MAR or MNAR) can be identified these should be used to
guide the imputation. Validation of the model should include missing
data to ensure the imputation and model is handled well in independent 
samples.  As @JWH2006 points out the extent of missingness will also affect your choice of tool - the lower the proportion of observations the riskier imputation becomes, requiring more powerful methods.

*If your variable types allow it, you can recode missing data to a new
numeric level in X that does not otherwise arise. This implicitly
handles the impact of missingness and will capture an element of any
bias that exists. This should mitigate against missingness bias in all three categories.

*A mashup of 2 and 3 alongside imputation you can create a Xmissing variable (e.g.
0 observed, 1 missing) that will be given its own model coefficient
and confidence intervals to explicitly handle the missingness. Again, this should mitigate against bias in the missingness.

*If
there is the possibility of revisiting the data source (even for a
partial sample of the missing and complete samples) and reacquiring
it then this may be useful to better understand the mechanism of
missingness to make a more robust procedure. Above I suggested some approaches can mitigate against bias, but they will never be guaranteed to eliminate its effect. If there is any way to go back and fill in the blanks it will improve your understanding of how the missingness arose and therefore give clues on how to handle it best. 


Remember
It also matters if the data is truly missing as opposed to something like not-applicable, not-detected or a saturation event. Not detected events are usually recoded to half the detection limit. Saturation events usually set to the saturation threshold.
A: The answer is "Yes". If you both train and apply your model only on the samples with non-missing $x$, then it is totally OK. Your single heroic assumption here is that the process that makes $x$ be missing is the same for the training and test data, which is quite reasonable.
If you want to train and apply your model on any data (both with and without missing values), there is a preprocessing scheme with wich popular families of models (linear, neural network, decision trees and their ensembles) can work adequately. You impute missing $x$ with any value you want (e.g. 0), and at the same time you create a binary marker of missingnes for each column with potential missing values. For example, the table
x1    x2
0     1
2     nan
3     1
nan   0
nan   nan

turns into
x1    x2    x1m   x2m
0     1     0     0
2     0     0     1
3     1     0     0
0     0     1     0
0     0     1     1

In this case e.g. a linear model would find values for coefficients to x1m and x2m which give the best prediction, even if the values are missing not-at-random.
A: The answer is - it depends. 
The issue with missing data and leaving it out of your model completely is that it might affect the representativeness of your sampled data. 
The kind of deletion you are referring to in your question is known as listwise deletion. This is where you exclude an observation completely because for at least one of your observed variables you do not have any data. Leaving out this data point might introduce bias into your model. 
I will illustrate with an example: One common way this occurs is in surveys and is known as a non-response bias. Participants might not answer certain sensitive questions such as "Are you HIV positive?" etc. So in your model if you leave out all the unanswered questions you might think that there is a low incidence of HIV in your sample but this might simply be wrong.
In essence dealing with missing data comes down to understanding why the data point is missing at all: Is it random or is it systematic? 
There are ways to find out if the missing data is systematic or not and the approach is similar to @David Dale's suggestion. You introduce new missing variables that indicate wether a data point is missing or not. We can then compare the mean likelihood of y for the 1’s and 0’s (missing and non-missing). If there is a significant difference in means, we have evidence that the data is not missing at random.  In other words, there’s a pattern to the missingness. This is the first type of missing data pattern called missing not at random (MNAR).
If there is no significant difference in means, between our primary variable and y then we have evidence that the data is missing at random (MAR).  
And finally, if there is no signifact difference in means between all our variables (primary and not) and the y then we have evidence that the data is missing completely at random (MCAR). This is the most desirable situation to be in.
If your data is MNAR then you will affect your model by listwise deletion of those values.
