Random Forests, Decision Trees, and Categorical Predictors: The “Absent Levels” Problem (PDF).
This problem occurs whenever there is an indeterminacy over how to handle an observation that has reached a categorical split which was determined when the observation in question’s level was absent during training.
TL;DR No feature engineering heuristics seem to really help mitigate this kind problem.