So I have found quite a few posts on the web including this Nintex Learn more article:
Task Lock - Task is locked by a running workflow and cannot be edited
But no real solutions. So we have been able to replicate this error on several different sites and with several different workflows which use lazy approval. The error only occurs when people reply to the lazy approval right away (within the first 3-4 minutes) and even then, only occurs about 10% of the time. It would appear what is happening is the task is still locked by the workflow when the lazy approval email is received, which generates the 'This task is locked by another user' error message.
But in each case, the lazy approval email is still processed and the workflow completes. It's basically just an annoyance that this email is randomly being sent out on some of the lazy approvals. Essentially the this task is locked by another user error email would appear to be sent prematurely in these cases.
Does anyone know of any solution to this problem?