Missing Categorical Features - no imputation
Certain models are able to deal with missing values 'naturally', like certain tree based models. Most models however are just a mathematical function which is shaped after the training data. A very easy example would be:

$$f(x) = \alpha x_1 + log(2x_2)$$

What do you do if one of them is NaN? The function is undefined and no prediction can be made. By imputing the values you make a reasonable guess where this sample lies on the data manifold.