We present radio and submillimetre observations of the O4I(n)f star zeta Pup, and discuss structure in the outer region of its wind ( ~ 10-100 R_*). The properties of bremsstrahlung, the dominant emission process at these wavelengths, make it sensitive to structure and allow us to study how the amount of structure changes in the wind by comparing the fluxes at different wavelengths. Possible forms of structure at these distances include Corotating Interaction Regions (CIRs), stochastic clumping, a disk or a polar enhancement. As the CIRs are azimuthally asymmetric, they should result in variability at submillimetre or radio wavelengths. To look for this variability, we acquired 3.6 and 6 cm observations with the Australia Telescope Compact Array (ATCA), covering about two rotational periods of the star. We supplemented these with archive observations from the NRAO Very Large Array (VLA), which cover a much longer time scale. We did not find variability at more than the +/-20% level. The long integration time does allow an accurate determination of the fluxes at 3.6 and 6 cm. Converting these fluxes into a mass loss rate, we find dot M = 3.5 x 10-6 Msun/yr. This value confirms the significant discrepancy with the mass loss rate derived from the Halpha profile, making zeta Pup an exception to the usually good agreement between the Halpha and radio mass loss rates. To study the run of structure as a function of distance, we supplemented the ATCA data by observing zeta Pup at 850 mu m with the James Clerk Maxwell Telescope (JCMT) and at 20 cm with the VLA. A smooth wind model shows that the millimetre fluxes are too high compared to the radio fluxes. While recombination of helium in the outer wind cannot be discounted as an explanation, the wealth of evidence for structure strongly suggests this as the explanation for the discrepancy. Model calculations show that the structure needs to be present in the inner ~ 70 R_* of the wind, but that it decays significantly, or maybe even disappears, beyond that radius.