The presence of missing response values complicates statistical analyses. However, incomplete data are particularly problematic when constructing optimal designs, as it is not known at the design stage which values will be missing. When data are missing at random (MAR) it is possible to incorporate this information into the optimality criterion that is used to find designs. However, when data are not missing at random (NMAR) such a framework can lead to inefficient designs. We first investigate an issue common to all missing data mechanisms: The covariance matrix of the estimators does not exist, so it is not clear how well the inverse of the information matrix will approximate the observed covariance matrix. To this end, we propose and study a new approximation to the observed covariance matrix for situations where the missing data mechanisms is MAR. We then address the specific challenges that NMAR values present when finding optimal designs for linear regression models. We show that the optimality criteria will depend on model parameters that traditionally do not affect the design, such as regression coefficients and the residual variance. We also develop a framework that improves efficiency of designs over those found assuming values are MAR.