Rudy,
If I understand your question correctly, you want to:
 cross correlate two downsized images to get a first guess of the shift
 Use the first guess to improve the speed of crosscorrelation on the fullsize images
Presumably the ideal outcome would be an improvement in the speed of your crosscorrelation, whilst still getting the same accuracy as using crosscorrelation from the full size image?
Firstly, it would have helped that you described the problem a bit clearer, giving exact function names (I presume you're using xcorr2?) and perhaps an example of your current code.
Assuming that my interpretation is right, there are a few different answers/comments that are relevant:

1. No, as it's not possible to directly provide xcorr2 with an initial guess (see help xcorr2).

2. It is possible to indirectly provide a guess: The best bet would probably be to round your initial guess to the nearest number of pixels, then use the circshift() function to move your second fullsize image by that amount. Then submit your first image and the moved second image to xcorr2. Add whatever shift you get as a result to the input guessed shift.

3. NUMBER 2 PROBABLY WON'T HELP... If anything, it'll be slower due to the additional overhead of shifting the image. The problem is that the majority of processing overhead for a cross correlation isn't in the peak finding routine (IF IT IS, THEN YOU NEED TO FIND A BETTER PEAK FINDING ROUTINE!!!!)  the majority of overhead is in the FFT, conjugation, multiply, and IFFT process which is the core algorithm of a cross correlation. Thus, if you do use the full size image at any stage, you will have to accept that overhead regardless of your initial guess. You can find out which bits of your code are taking the longest time using the profiler and/or the tic/toc functions.

4. If you're desperate for speed, have a fairly recent NVIDIA graphics card, and are certain you want to use a fullres image, you could write you're own cross correlation algorithm, which would go something like this:
% Load images:
A = double(imread('A.jpg'))
B = bouble(imread('B.jpg'))
% Normalise if necessary
% insert normalisation here if you want it...
% see help('xcorr') for a good explanation
% Take FFTs
S = fft2(A)
T = fft2(B)
% Conjugate T and multiply with S
T = S.*conjg(T)
% Take IFFT
C = ifft2(T)
% Find CC peak
% Use your own peak finding algorithm,
% or one here on the FEX (there are loads)
% to find the maximum peak location,
% which represents your image shift.
NOTE that this won't be any faster than xcorr2 (probably slower) unless you have a reasonable NVIDIA card. if you do, however, search for and install the 'Matlab plugin for CUDA' which overloads Matlab's FFT and IFFT functions to do the processing on the graphics card. This will give you a 10x  14x speed increase.
NOTE also that you may need to circshift() the FFTs and cast complex C to real. I can't remember, and don't have MATLAB in front of me so can't find out!

5 I know you said you can't use subwindows, but if you were fairly sure that your subwindows were bigger than the black spots, it wouldn't matter.

6. I don't know the insandouts of your sample preparation, but I'd say there's a good possibility that your sample expands as well as shifting. In that case, a windowed crosscorrelation could be much more effective than a wholeimage correlation, even if you only divide your image into 4 quarters.
Hope this helps!
Tom Clark
