For a natural immunity to evolve, two things have to happen:
The immunity has to actually occur. That means all the necessary mutations will need to be there to grant this bacterium resistance to penicillin. For penicillin, for example, bacteria that evolved such a resistance evolved to produce the enzyme beta-lactamase.
The immunity has to grant an advantage. Penicillin is produced by Penicillium, which is a mold found in environments with lots of oxygen. Lots of bacterial species have never encountered penicillin and the vast majority (for example anaerobic bacteria that don't infect humans) never will. In the absence of this pressure, a resistance to penicillin, even if it evolves, will likely deteriorate within a few generations because the individuals with the resistance do not have an advantage in survival. Producing an enzyme such as beta-lactamase is not without its costs (protein synthesis).
While bacteria van exchange genetic material in the form of plasmids between different species, so not all species would need to evolve beta-lactamase de novo, this is also only "helpful" if the bacteria a) come in contact with resistant bacteria species, and b) if this resistance confers an advantage for the receiving species.
Origins and Evolution of Antibiotic Resistance
Mechanisms of Bacterial Resistance to Antibiotics