Late recommendation letter
Question 1: When job ads on mathjobs say something like "screening of applications will begin on November 1", do they really mean it, or do they mean something like "screening of applications will begin on mid December, but we want you to submit your application early"?


It depends on the department.  It is however well known that many faculty members drag their feet with recommendation letters, and this happens more or less independently of the quality of the applicant.  So in my experience it is common to allow a grace period of a couple of weeks to allow the letters to trickle in.


  Question 2: What would you do in my situation (assuming that the relevant letter writer is currently abroad and I have no other way to contact him)? Should I contact the relevant search committees and ask them to check that reference letter a bit later, once it gets updated?


Frankly I think you're too worried about the entire situation.  You did some exciting new work: great.  All but one of the letters will describe this exciting new work.  The other letter may not.  So when people read the letters they will see that your exciting new work is so new that one of your writers is a little out of the loop.  I see no big problem here.  If one of the letters is more negative than the others, that drags your application down.  If one of the letters is less informative than the others...frankly, that usually happens and is really much of the reason why you get multiple letters. 


  Question 3: If a letter of recommendation is updated on mathjobs past the submission of an application, which version of the letters is available to the search committee? What should I do in order to make sure that they read the updated version?


Hmm.  I believe what happens is that if the file has not been read by anyone, the letter updates without recording the change.  If it has been read, then both versions of the letter appear.  But I am not completely sure about this.

In summary: you solved some well-known open problems in your field. That's the dream.  You say that this will probably turn your application from "good" to "outstanding."  Well, I agree.  Congratulations, and I hope you enjoy your postdoc.