Job prospects in case of an unwelcoming mentor
Having a strained relationship with his past mentors (both PhD and postdoc) is definitely going to put Jim at a disadvantage on the job market.  But that doesn't mean he has no chance at finding a decent faculty position.  Here's what I would recommend.  This is aimed at looking for faculty positions in the US, where recommendation letters are mandatory and crucial; hiring practices in other countries are different.


Ask directly.  Worrying that the supervisor won't send letters or won't write a strong letter is pointless.  Jim must ask his supervisor directly, in person, face to face, if they are willing to provide a strong letter of recommendation.  He should also make it clear that to simplify their work and preserve his sanity, he will provide a mechanism to track letter requests (see next).  If the supervisor agrees, Jim should immediately send email confirming the agreement.
Track letter requests.  Jim should provide an online spreadsheet (via Google Docs, for example) that lists all the positions Jim has applied to, one per row, with contact information and deadlines, and a column for each reference.  Then references can indicate in their column which letters they have sent and when.  Tracking not only relieves Jim's uncertainty; it also drastically simplifies the job of his references.  It also provides a public shaming mechanism, since Jim and all his references can see who has or hasn't sent which letters.  (This is not just a suggestions for Jim; everyone on the academic job market should do this.)
Use a letter service like https://www.interfolio.com/ or https://academicjobsonline.org/ , which allow applicants to track the status of letter requests, and provide interfaces for references to upload confidential (generic) letters and for departments to retrieve them directly.  Again, this both lowers stress for the applicant and simplifies the work of the references.  Not all departments trust these services—some people prefer to communicate directly with references—so this can't be the only tracking mechanism.  On the other hand, some departments actually require using these services, so Jim may as well use them anyway.
Double-check with departments. If Jim is really worried that his supervisor is lying when he says he's provided the letter, he should ask a few departments to confirm that they have received all their requested letters.  Not all will reply, and some departments may be vague (because they need to keep confidential whether they've requested letters at all, or which of your N references they've asked), but enough will reply that Jim can either rest easy or know for sure that his supervisor is a dishonest jerk.  (In that case, Jim should update the tracking spreadsheet to indicate which letters were "sent" but not actually received.)
Find good references from the research community.  Since Jim already has several years of postdoc experience and a nontrivial publication record ("one paper per year in a high-rank computer science conference or journal"), he is already known in his research community through his work.  At this point in his academic career, most of Jim's references should not be supervisors, coauthors, or other faculty at his previous institutions they should be arms-length experts in his field who can give an independent evaluation of his research record.  Jim should ask for letters from experts who have given him positive feedback in the past, either by citing and building on his work, or by offering supporting comments in person at conferences.  (Ideally, Jim started cultivating these outside experts as potential references when he was still a PhD student, but better late than never.)  Remember that a normal part of asking for references is asking for suggestions for where to apply.
Have more references than required.  Most US departments ask for three recommendation letters.  Under normal circumstances, I'd suggest finding at least four references, so if someone doesn't reply you have a backup.  If Jim is worried that some references won't actually send letters, he should find five.  (That said, some departments only allow applicants to specify three references, or only request letters from the first three of N the applicant provides, so it's important to prioritize.)
Apply broadly. The application process is random; crudely, the most lottery tickets you buy, the more likely you are to win.  Not having a letter from his most recent survey would be a red flag, but that just lowers the chances of any particular application panning out.  Jim can counter that effect by applying to more positions.



  What incentives could cause a previous mentor to actually send a reference letter rather than simply replying "done" or moving the request to the trash bin?


Professional embarrassment.  After all, your other references will know that he agreed to write letters for you.  Being known as a dishonest jerk will not be good for Jim's supervisor's career.


  Each proper job application for a tenure-track position takes Jim a couple of full working days, so he is not wishing to invest his time into something which is doomed to fail.


It really shouldn't take that long, at least for tenure-track positions at US research universities.  Most of the successful faculty applications I see (in 15+ years on my department's hiring committee) are at most minimally tailored to my department, except possibly for the cover letter (which almost nobody reads).  In particular, the CV should be a complete record, and therefore identical for every application except possibly for order: research first for research-focused positions, teaching first for teaching-focused positions.  The research and teaching statements should confidently focus on Jim's accomplishments and vision.  Uploading the documents should only take a few minutes.