Deadlock?

[Del]

Anybody have an idea how I could get a deadlock situation?
Two different operators running two different pgms both tried to lock the 
same record at the same time (lookup with -p flag).
They BOTH got the 'waiting for record to be unlocked' message.
Both sessions hung until I killed one, then the other took off.
The first one in should get the record, the second should get the 'waiting' 
message.
Is there some stupid thing I am doing that could cause this?
It seems to me that there is no way I should be able to cause this, no 
matter what I did.

Seeking illumination.

Del