This situation occurs if all your threads are waiting only on one object - in your case it seems, that it is mutexRecords. Any
thread, which unlocks any record causes all waiting threads to become alive (by using notifyAll()) and all threads must check status of record they are trying to lock. Other reason is spurious wake-up.
This approach should be OK, Andrew's book says, that per-record locking is probably not required.
Did you make this
test with 2 threads only? Can you investigate reason why 2nd thread wakes up multiple times? I suggest to add thread name to any traces you make.