We present sensitive CO (J = 1 - 0) emission line observations of three metal-poor dwarf irregular galaxies Leo P (Z ~ 3% Z_Solar), Sextans A (Z ~ 7.5% Z_Solar), and Sextans B (Z ~ 7.5% Z_Solar), all obtained with the Combined Array for Millimeter-wave Astronomy (CARMA) interferometer. While no CO emission was detected, the proximity of the three systems allows us to place very stringent (4 sigma) upper limits on the CO luminosity (L_CO) in these metal-poor galaxies. We find the CO luminosities to be L_CO < 2900 K km/s pc^2 for Leo P, L_CO < 12400 K km/s pc^2 for Sextans A, and L_CO < 9700 K km/s pc^2 for Sextans B. Comparison of our results with recent observational estimates of the factor for converting between L_CO and the mass of molecular hydrogen, as well as theoretical models, provides further evidence that either the CO-to-H_2 conversion factor increases sharply as metallicity decreases, or that stars are forming in these three galaxies very efficiently, requiring little molecular hydrogen.