The query returns approx 20000 records (from same table). And I'm running 10 parallel instances of the application, each returning 20000 records.

But the order by clause is on the primary key (UKP actually) on the table.
So records being fetched & locked in various orders should not happen theoritically.