I assume your regression model is of the form:
Where X1 and X2 are categorical variables.
You dont need data for all combinations because the assumption of the (basic) OLS model is that the effect of each variable on E(Y) is independent of the values of the other variable (unless you use combined indicators, but you haven't said anything to suggest you intend to do that).
Of course the assumption in italics is strong and you will have a weaker chance of detecting any error if you dont collect data from all combinations of caategories.
Does that make sense?