Cross-correlation of time compressed 1D signal
With known time scaling, you can resample to a common rate and then cross-correlate.  It is natural to think you might need to go to the higher of the two rates, but that does not increase information beyond the lower rate, it only interpolates the information. This is analogous to zero-padding an FFT to interpolate the resolution of a peak.

To determine unknown time scaling, cepstral processing may provide some insights.  I'm afraid it is not my area, but it sounds related to what you are describing.

Essentially, you've got two dimensions of uncertainty (start time, rate) across which you'd like to search to find the best correlation.

You can reduce it to one dimension by considering the magnitude of the two signals' spectral data. The lower rate data should then look like a stretched version of the higher rate data.