Stochastic search variable selection (SSVS) algorithms provide an appealing and widely used approach for searching for good subsets of predictors while simultaneously estimating posterior model probabilities and model-averaged predictive distributions. This article proposes a two-level generalization of SSVS to account for missing predictors while accommodating uncertainty in the relationships between these predictors. Bayesian approaches for allowing predictors that are missing at random require a model on the joint distribution of the predictors. We show that predictive performance can be improved by allowing uncertainty in the specification of predictor relationships in this model. The methods are illustrated through simulation studies and analysis of an epidemiologic data set.