The fraction of compact active galactic nuclei (AGNs) that exhibit interstellar scintillation (ISS) at radio wavelengths, as well as their scintillation amplitudes, have been found to decrease significantly for sources at redshifts z > 2. This can be attributed to an increase in the angular sizes of the muas-scale cores or a decrease in the flux densities of the compact muas cores relative to that of the mas-scale components with increasing redshift, possibly arising from (1) the space-time curvature of an expanding Universe, (2) AGN evolution, (3) source selection biases, (4) scatter broadening in the ionized intergalactic medium (IGM) and intervening galaxies, or (5) gravitational lensing. We examine the frequency scaling of this redshift dependence of ISS to determine its origin, using data from a dual-frequency survey of ISS of 128 sources at 0 < z < 4. We present a novel method of analysis which accounts for selection effects in the source sample. We determine that the redshift dependence of ISS is partially linked to the steepening of source spectral indices ({alpha}^8.4_4.9) with redshift, caused either by selection biases or AGN evolution, coupled with weaker ISS in the {alpha}^8.4_4.9 < -0.4 sources. Selecting only the -0.4 < {alpha}^8.4_4.9 < 0.4 sources, we find that the redshift dependence of ISS is still significant, but is not significantly steeper than the expected (1+z)^0.5 scaling of source angular sizes due to cosmological expansion for a brightness temperature and flux-limited sample of sources. We find no significant evidence for scatter broadening in the IGM, ruling it out as the main cause of the redshift dependence of ISS. We obtain an upper limit to IGM scatter broadening of < 110muas at 4.9 GHz with 99% confidence for all lines of sight, and as low as < 8muas for sight-lines to the most compact, sim 10muas sources.