We employ CaII K and NaI D interstellar absorption-line spectroscopy of early-type stars in the Large and Small Magellanic Clouds (LMC, SMC) to investigate the large- and small-scale structure in foreground intermediate- and high-velocity clouds (I/HVCs). Data include FLAMES-GIRAFFE CaII K observations of 403 stars in four open clusters, plus FEROS or UVES spectra of 156 stars in the LMC and SMC. The FLAMES observations are amongst the most extensive probes to date of CaII structures on ~20-arcsec scales in Magellanic I/HVCs. From the FLAMES data within a 0.5{deg} field of view, the CaII K equivalent width in the I/HVC components towards three clusters varies by factors of >=10. There are no detections of molecular gas in absorption at intermediate or high velocities, although molecular absorption is present at LMC and Galactic velocities towards some sightlines. The FEROS/UVES data show CaII K I/HVC absorption in ~60 per cent of sightlines. The range in the CaII/NaI ratio in I/HVCs is from -0.45 to +1.5dex, similar to previous measurements for I/HVCs. In 10 sightlines we find CaII/Oi ratios in I/HVC gas ranging from 0.2 to 1.5dex below the solar value, indicating either dust or ionization effects. In nine sightlines I/HVC gas is detected in both Hi and CaII at similar velocities, implying that the two elements form part of the same structure.