This research focuses on performing ultrasound propagation measurements and micro-X-ray computed tomography (µXRCT) imaging on prestressed granular packings prepared with biphasic mixtures of monodisperse glass and rubber particles at different compositions/fractions. Ultrasound experiments employing piezoelectric transducers, mounted in an oedometric cell (complementing earlier triaxial cell experiments), are used to excite and detect longitudinal ultrasound waves through randomly prepared mixtures of monodisperse stiff/soft particles. While the fraction of the soft particles is increasing linearly from zero, the effective macroscopic stiffness of the granular packings transits nonlinearly and nonmonotonically toward the soft limit, remarkably via an interesting stiffer regime for small rubber fractions between 0.1 ≲ ν ≲ 0.2. The contact network of dense packings, as accessed from µXRCT, plays a key role in understanding this phenomenon, considering the structure of the network, the chain length, the grain contacts, and the particle coordination. While the maximum stiffness is due to surprisingly shortened chains, the sudden drop in elastic stiffness of the mixture packings, at ν ≈ 0.4, is associated with chains of particles that include both glass and rubber particles (soft chains); for ν ≲ 0.3, the dominant chains include only glass particles (hard chains). At the drop, ν ≈ 0.4, the coordination number of glass and rubber networks is approximately four and three, respectively, i.e., neither of the networks are jammed, and the chains need to include particles from another species to propagate information.