Would you rather worry that a professor will forget to write your letter of recommendation before application review begins, or discover that a professor has sent out your letters when you haven't prepared your application yet?
Four years of graduate school have trained me well when interacting with faculty. I know that if I show up five minutes after the scheduled start of any weekly meeting or colloquium, I will not be "late", because many faculty will still be on their way. I know that my committee members want any drafts at least one and preferably two weeks in advance, but will not read the drafts until the night before, or possibly the morning of the meeting.
Knowing the usual turnaround time for requests from faculty, I made my requests for recommendation letters as soon as I found jobs worth applying for, all with deadlines in mid-October. Two and a half months' notice seemed about right: Enough time for the faculty to write two or three pages enthusing about my teaching or research skills, but not so much time that they might forget or misplace the request. The challenge is that with three different professors, I get three different responses.
The first letter was requested of my advisor. Her response typifies what I have come to expect of faculty; hardly surprising, I suppose, when she's the faculty member with whom I interact the most. She responded by instructing me to keep our lab coordinator copied on all these emails, a necessary step to make sure she meets the deadlines. Two and a half months is cutting it a bit close for the busy faculty member just starting her sabbatical.
The second letter was requested of the instructor for whom I taught an advanced laboratory course. I asked in person, and received an enthusiastic agreement and instructions to tell him exactly what he wanted me to say. I emailed the list of addresses, and have heard nothing since. In a few weeks, when the hectic start of the semester is over, I'll arrange to pass him in the hallway, and check up on the letters as part of the small talk.
The third letter was requested from a the director of my school's graduate teaching office. Here is where I got my surprise, a faculty member who had been trained to deal with student requests in a timely and efficient matter. Barely a week after I made the request, I got an email - the letters had been sent. I had barely thought about my cover letters, and colleges would receive a letter endorsing me within a few days.
This certainly provided the impetus for me to get on with my applications. A week and a half later, I had written, revised and finalized my cover letter, and finished revising my teaching and research statements. Surely the search committee, or whichever staff member was delegated to deal with the incoming mail, could not hold such a brief delay against me. After all, there were graduate schools who received my GREs and nothing else.
As panicked as I was the first three days after I learned the letters had already been sent, I find I much prefer the faculty member who is completely on top of such things. I will spend the next two months worrying whether the other letters have been written or sent; given the choice between a brief panic and a lingering mild worry, I'll take the brief panic any time.