@ Davy: Is the spread within your delay range? You don't use averages, you find the range into which your delay usually falls (e.g. for me it is 617-623). You shouldn't be searching for spreads outside your delay range.
Are you using RNG for Egg IVs? if so, there is almost always at least one spread within your range, given the right parents (but you can RNG the parents too). Are you also searching all frames greater than the one you are saved on with the same odd/evenness? (i.e. for frame 3, also search 5, 7, 9, 11 etc...).
If you can still only find that spread, as a last resort, you can shift the delay of the spread by adjusting the year. To add 12 to the delay of a spread, set the clock back 12 years. The target date and time are otherwise unchanged.
@ Andralexis: Yes, this works on all 4th generation Pokemon games.