Multiple Features with the same categorical value
The increase in dimensionality due to 'No Internet Service' could be handled maybe with a 2 layer model. If 'No Internet Service' is true, you run the first level model with a handful of other variables (excluding those which depend on internet service availability). The second layer model runs only when internet service available, with all the variables.