Good call, implicit conversion of the order_id to char supresses the index, and thus the key range locks on all rows.  Changing the stored procs fixed the issue.

From:

and...