In robust design, it is important not only to achieve robust design objectives but also to maintain the robustness of design feasibility under the effect of variations (or uncertainties). However, the evaluation' of feasibility robustness is often a computationally intensive process. Simplified approaches in existing robust design applications may lead to either overconservative or infeasible design solutions. In this paper, several feasibility-modeling techniques for robust optimization are examined. These methods are classified into two categories: methods that require probability and statistical analyses (i.e., the probabilistic feasibility formulation and the moment matching method) and methods do not require probability and statistical analyses (i.e., the worst case analysis, the comer space evaluation, and the variation pattern method). Using illustrative examples, the effectiveness of each method is compared in terms of its efficiency and accuracy. Constructive recommendations are made to employ different techniques for modeling feasibility robustness under different circumstances. Under the framework of probabilistic robust optimization, we propose to use a most probable point (MPP) based importance sampling method, a method rooted in the field of reliability analysis, for evaluating the feasibility robustness. The advantages of this approach are discussed. Though our discussions are centered on robust design, the principles presented are also applicable for general probabilistic optimization problems. The practical significance of this work also lies in the development of efficient feasibility evaluation methods that can support quality engineering practice, such as the Six Sigma approach that is being widely used in American industry.