Monthly salary payments for a payroll service

Your company runs payroll for 1,200 small employers. On the last working day of each month, a job pays every employee's net salary through a bank's payments API. That is about 40,000 payments in one run. Each call takes about 300 ms, and the bank allows 20 calls at a time. Sometimes a call times out without saying whether the payment went through.

Last month the job crashed partway through. Someone restarted it from the top, and 6,000 people were paid twice. Each payment can carry a reference of up to 35 characters. The bank refuses a payment whose reference it has already accepted in the last 90 days, with a duplicate reference error. Salaries must reach the bank by 14:00 on payment day.

How do you run the payments so each person is paid once and only once, through crashes and bank timeouts?