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.

There's no guarantee that BP with PoolSize=1 would process messages in enqueued order. That is only true for BOs, for BPs it's only true that message processing would start in the enqueued order. That might be (or might be not) a good enough guarantee for you depending on your use case.

An approach I saw used to guarantee FIFO for BP is to add an intermediate BP with PoolSize=1 which sends a sync request to your target BP and waits for an answer.  

Can you elaborate on a Message key, please? Is it a random or a categorical division? Why three specifically and not some other number?

What we were considering doing is increasing the pool size to 3 and programmatically creating a BPL on each thread that processes messages that would be directed to it, rather than having to create multiple BPLs into the production.

What do you want to achieve with that change?

%Library.RoutineMgr_StudioOpenDialog is a useful query!

Originally I started writing something similar, but went into %Dictionary package instead, which of course created issues for me about System and Mapped classes, so I decided to go a different way (ended with what's presented in this article).

With your approach I'll advice first building a list of classes to delete and then passing it to $SYSTEM.OBJ.Delete - it will be faster than deleting classes one by one. That said usually deletions are small in number (or at least in frequency) so speed does not really matter here.