  We employ CaII K and NaI D interstellar absorption-line spectroscopy of
early-type stars in the Large and Small Magellanic Clouds to investigate the
large- and small-scale structure in foreground Intermediate and High Velocity
Clouds (I/HVCs). These 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
  From the FLAMES data within a 0.5 degree 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 sightlines show variations in EW
exceeding a factor 7 in CH+ towards NGC 1761 over scales of less than 10
arcminutes.
  The FEROS/UVES data show CaII K I/HVC absorption in $\sim$60 per cent of
sightlines. No NaI D is found at non-Magellanic HVC velocities aside from a
tentative detection towards the star LHA 120-S 93. The range in the CaII/NaI
ratio in I/HVCs is from -0.45 to +1.5 dex, similar to previous measurements for
I/HVCs.
  In ten sightlines we find CaII/OI ratios in I/HVC gas ranging from 0.2 to 1.5
dex below the solar value, indicating either dust or ionisation effects. In
nine sightlines I/HVC gas is detected in both HI and CaII, and shows similar
CaII/HI ratios to typical I/HVCs, and similar velocities, implying that in
these sightlines the two elements form part of the same structure.
