How about the following setup:

1. In Business Service or first router BP set a global: ^data(mrn, timestamp) = messageId
2. In your FIFO BP before sending to BO check: 
   • set nexttimestamp=$o(^data(mrn,""),1,nextmessageId)
3. If nextmessageId equals current messageid that means there's no message in a pipeline for the same patient with earlier timestamp so we can send it out.
   • Kill  ^data(mrn, nexttimestamp) so next message can be processed 
4. If nextmessageId does not equal current messageid, compare timestamps:
   • If timestamps are equal, send the message anyway and don't kill the subscript - we have more than one message with the same timestamp. If it happens often, value should be a list of ids.
   • If nexttimestamp is earlier than timestamp, it means there are some other messages in a pipeline with the same MRN, sleep for 10 seconds and check again.

Notes:

1. You'll need to adjust this based on what you want to do if one of the messages errors before being deleted from the ^data global, options:
   • Processing of messages for this patient effectively stops.
   • Add an additional check in (4) - get other message header and check if it's in a final state (completed, errored, etc) - if so clear ^data subscript and continue.
   • Add an additional check in (4) -  if we waited more than X seconds, continue.
2. This can be wrapped as Custom Functions and called from rules, BPs.
3. Locks might help with ensuring consistency.

The advantage here is that you can scale to any number of jobs immediately and since you enforce FIFO only at the end, most of the processing can be parallelized.