As the question as been focused, I edit the answer in a three-fold way:
One first approach consists in (somehow) compensating the unknow delay, by applying the initial algorithm for several delays, and in comparing results. This can be done brute force or with optimization loops. One frequent filter design for such a task is known as the Thiran Allpass Interpolators. A Matlab implementation is given at: Thiran Allpass Interpolation in Matlab. A reference paper is J.-P. Thiran, Recursive digital filters with maximally flat group delay, 1971, IEEE Transactions on Circuits Theory.
A second approach may consist in finding a more invariant transformation. The phase suggested by @Richard Lyons is a very good option, since several Fourier transforms possess nice shift/time invariant properties. The two above methods can be extented with GCC or Generalized Cross Correlation, a link with nice background references (like Optimum Estimation of Time Delay by a Generalized Correlator, IEEE Trans. Acoustics, Speech and Signal Processing, 1979). They can also be merged, for instance with GCC-PHAT Cross-Correlation, including phase information.
Invariance is indeed a neat concept, and may be used as well using other signal properties (or non-properties). If the process under consideration is quite stationary, you can get good results with the methods above, up to an integer number of periods if the signal is periodic.
In the case the data is unstationary, has amplitude variations, gets noisy, other methods, or combinations, can be useful. Wavelets can deal with unstationarity. Some are quite shift-invariant. Some others are complex and provide local phase information.
I would suggest a combination of continuous complex wavelets and correlation, such as the one proposed in Time Delay Estimation Using Wavelet Transform for Pulsed-Wave Ultrasound, Annals of Biomedical Engineering, 1995. Other reference? On Wavelet Denoising and its Applications to Time Delay Estimation, IEEE Transactions on Signal Processing, 1999.
A careful reference analysis or the above mentioned concepts may provide you with other useful insights.
My personal experience is not global. It is mostly based on image processing experience, and a work on local delay adaptation for adaptive pattern subtraction in seismic data, using complex wavelets and very short one-tap (unary) complex phase filters, which proved to work quite well.