If its a requirement to process the messages in order, then implement singleton pattern. Only one instance of orchestration will process the messages.
But if its not, I guess you need analyze the causes for database locks and try to avoid them.
-try using stored procedures
-minimize the scope of database transaction