Four threads and the CPU-bound job takes the same time

The interpreter lock serialises bytecode execution, so threads help with waiting, not with computing. Processes are the fix for CPU-bound work:

from concurrent.futures import ProcessPoolExecutor

with ProcessPoolExecutor() as pool:
    results = list(pool.map(work, items, chunksize=64))

chunksize matters more than the worker count: without it, small tasks spend all their time being serialised between processes.

They take the same locks in different orders, and only concurrency makes that visible. Establish a global ordering, usually by sorting the ids you touch before touching them. Retry logic is a bandage: correct, necessary, and not a substitute for the ordering.