Yes, I would say how long to wait depends on both how far ahead it is promised and how important or urgent the work is. It depends what the situation warrants.
Urgent and Important Deadlines
You should absolutely convey the importance of the deadline beforehand, and probably also check in once or twice just to check on whether we are still on track for reaching the deadline, especially if there is much time to elapse in between. A nice touch would also be to offer to see whether there are any hurdles you can help clear up for them, before the deadline to help them reach it. This will help more than following up after the fact.
Keeping in mind why the deadline is urgent may help determine how quickly to follow up. Are there people in the lobby waiting for this document? Do you need this document to conduct an interview that is scheduled for 10:15?
In many cases, if the document is needed within minutes of the deadline, you may want to call on the phone to quickly clarify whether the document is almost ready and on it's way, or being necessarily delayed as, presumably, at 10:01 they are still so completely focused on finishing up with the urgent document that they are not checking their email ;-).
If on the other hand, you need to do a 4 hour task that has a hard deadline in response to their document, waiting a half hour to an hour to follow up after the deadline, would still give you plenty of time to complete your work, while giving them adequate time to finish up.
Less Urgent Deadlines
It's quite possible they didn't get to it because it got pushed aside for more urgent projects, or perhaps they just forgot to actually put it on their todo list. In this case, your follow-up might be more along the line of politely reminding them suggesting a specific deadline extension. "I didn't see that report yet, just wanted to make sure it hasn't fallen off the radar. Would you like me to follow up again next Tuesday?" Something that if they are swamped they could just answer with a one liner. A week or more extension, if it's not a big deal for you, might be very helpful to the other person if they have more urgent deadlines.
In this scenario, several hours to a day later, or even a week, would not be an unreasonable amount of time to wait until after the deadline to follow up. Should you feel like following up much closer to the deadline, you could always blame your "outlook reminder" for reminding you to follow up, rather than leaving it to seem like you're hounding them to hurry up and finish.
In any case, how you word your response may make a world of difference in whether you sound annoyed they aren't done yet, concerned about their workload, understanding that they're busy, and so forth. So focus on the tone of your follow-up more than the when.