Do you have the main domain in the sites domain box? If so is it just the domain or do you have HTTP(s) or anything like that in there? The value should be something like www.domain.com or domain.com.
Secondly, what do you have for domain aliases? Is it possible that your aliases are being called an don't have a proper DNS entry setup or maybe those aliases are setup like I first mentioned?
Lastly and probably more important, do you have the scheduler running custom code? If so, have you attempted to put in some event logging to give you more info into the scheduled task?
I'm not 100% any of these will help resolve the problem, but these are things I've had issues with the scheduling engine in the past so figured I'd pass along.