Is it ever recommended to use mean/multiple imputation when using tree-based predictive models? Everytime that I am making some predictive model and I have missing data I impute categorical variables with something like "UNKNOWN" and numerical variables with some absurd number that will never be seen in practice (even if the variable is unbounded I can take the exponent of the variable and make the unknown values negative).
The main advantage is that the model knows that the variable is missing, which is not the case for say mean imputation. I can see that this could be disastrous in linear models or neural networks but in tree-based models this is handled really smoothly.
I know that there is a great deal of literature on missing data imputation, but when and why would I ever use these methods when missing data for predictive (tree-based) models?
 A: One reason you may not want to use "insert impossible value" methods is that means that your predictive model works conditional on the distribution of the data missingness remaining unchanged. Thus, if after building your tree model, it is realized that we can start using certain features more often, we can no longer use the model that was built using the "impute impossible value" method without retraining the model. 
In fact, this problem is even further compounded if the rates of missingness changes during the data collection process itself. Then, even immediately after building the model, it is already "out of date", as the current rates of missingness will be different than the rates of missingness during when the data was collected.  
To illustrate the issue, let's suppose a bank is building a database to help predict if clients will default on a loan. Early in the data collection process, loan officers have the option to conduct a background investigation, but they almost never do for clients they deem as trustworthy. Thus, for the especially trustworthy customers, the background check variable is almost always missing. If you use the "impute impossible value" method, having a non-missing value for background checks indicates high risk. 
If background check rates don't change at all, then this "impute impossible value" method will likely still provide valid predictions. However, let's suppose the bank realizes that background checks are really helpful for assessing risk, so they change their policy to include background checks for everyone. Then, everyone will have a possible value for background checks and using the "impute impossible value" method, everyone will be flagged as "high risk". 
Cross validation will not catch this issue, as the missingness distribution will be the same between the training and testing sets. So even though the "impute impossible value" method may lead to pretty results during cross-validation, this will lead to poor predictions upon deployment!
Note that you will essentially need to throw away all your data everytime your data collection policy changes! Alternatively, if you can correctly impute the missing values and their uncertainty, you can now use the data that was collected under the old policy. 
A: I disagree. You can use "missing" as an additional set of information, just as anything else. Imputation, in this case, emphasizes the lack of information along some dimension in your sample. That could have additional explanatory power.
The issue is more that "missing" will become a dichotomic variable and mixing it with continous one can lead to inefficient state space segmentation in the way the regression trees are constructed. The key is to force the tree to only split dichotomically too, too increase efficiency. In other words, your split decision is already known beforehand.
It does not really matter whether the frequency of the missing values increase or decrease. This is more related to the problem being stationary or not and has nothing specifically to do with the decision tree.
Non-stationarity is handled via updating of decision trees or using an ensemble of decision trees.
