We investigate effects of ordinary nonmagnetic disorder in the bulk of a superconductor on magnetic adatom-induced Shiba states and on the proximity-induced superconductivity in a nanowire that is tunnel coupled to the bulk superconductor. Within the formalism of self-consistent Born approximation, we show that, contrary to widespread belief, the proximity-induced topological superconductivity can be adversely affected by the bulk superconducting disorder even in the absence of any disorder in the nanowire (or the superconductor-nanowire interface) when the proximity tunnel coupling is strong. In particular, bulk disorder can effectively randomize the Shiba-state energies. In the case of a proximate semiconductor nanowire, we numerically compute the dependence of the effective disorder and pairing gap induced on the wire as a function of the semiconductor-superconductor tunnel coupling. We find that the scaling exponent of the induced disorder with respect to coupling is always larger than that of the induced gap, implying that at weak coupling, the proximity-induced pairing gap dominates, whereas at strong coupling, the induced disorder dominates. These findings bring out the importance of improving the quality of the bulk superconductor itself (in addition to the quality of the nanowire and the interface) in the experimental search for solid-state Majorana fermions in proximity-coupled hybrid structures and, in particular, points out the pitfall of pursuing strong coupling between the semiconductor and the superconductor in a goal toward having a large proximity gap. In particular, our work establishes that the bulk superconductor in strongly coupled hybrid systems for Majorana studies must be in the ultraclean limit, since otherwise the bulk disorder is likely to completely suppress all induced topological superconductivity effects.