Here, we directly address the stability challenge in screening materials for CO2 and CH4 storage across a set of the hypothetical USMOF structures that capture the diversity of previously synthesized MOFs. Starting from the known subset of 9,524 ultrastable (i.e., in terms of thermal and activation stability) USMOF DB structures, we compute the mechanical strength and select the top 1,102 of these structures in terms of mechanical stability. We obtain CO2 and CH4 adsorption properties using GCMC and compare properties of these mechanically stable USMOF DB MOFs to experimental CoRE MOF 2019 DB structures. By training interpretable ML models, we identify and explain unexpected trends in the USMOF DB compared to the experimental CoRE MOF 2019 DB, namely a number of MOFs preferring CH4 over CO2 in the USMOF DB. Based on insights gained from these ML models, we propose design rules based on geometric features and node chemistry for MOFs in the USMOF DB to achieve alternately high or low relative CO2 vs. CH4 working capacity.