We demonstrate a novel method for measuring the microrheology of soft viscoelastic media, based on cross correlating the thermal motion of pairs of embedded tracer particles. The method does not depend on the exact nature of the coupling between the tracers and the medium, and yields accurate rheological data for highly inhomogeneous materials. We demonstrate the accuracy of this method with a guar solution, for which other microscopic methods fail due to the polymer's mesoscopic inhomogeneity. Measurements in an F-actin solution suggest conventional microrheology measurements may not reflect the true bulk behavior.