If you are bound to an existing database schema then there isn't much you can do (depending on how bound you are of course). That's a totally valid reason to choose your current path. I'm not naive to business requirements. Often, systems end up being far from theoretically perfect due to legacy {insert component of stack here}. I get it.

So ruling out a snapshot table (I think you have made clear this is not an option), your best choice would then be a transaction table where your [state] is a Type 2 Slowly Changing Dimension (SCD2) with an indicator field for the current state. I want to be clear here: you should be storing your state, NOT the events (arguments) that can be used to derive your state. I cannot express this enough. Your problem is not unique. You simply cannot be naive enough to think you are the first person to want store the state history of an FSM in a database. This is literally data warehousing 101. The novelty of your solution stems from the fact that you are (dangerously) misunderstanding the problem. If, for some reason, you need to store what [event_name] caused the transition to the [state], just add a field. Simple.

As for invariants. Let's use an example: say you add a "package" event that transitions to an [in_transit] state between [awaiting_shipment] and [shipped] (note here we may also then want to change "ship" to "deliver"). This simple and totally reasonable change would make every order with an event queue: "create", "pay", "ship" result in [error]. If you just stored the [state], then a [shipped] order will remain [shipped] regardless of what series of events brought it there - which would be correct. There would be no need to go back and change historical data - nor would you want to. How would that even be done? Manufacture shipping information and timestamps? There are no invariants in this process (again, I want to reiterate that this is a solved problem). True FSMs (if this is actually modeled as one) only care about the current state anyway and maybe the previous state (see SCD3). What I mean is, future actions are determined using the current state. If the current state becomes [error] for 1 billion orders, that's a problem. A huge problem.

"Absolute correctness" is an interesting term... and I agree that I am probably coming off a bit aggressive in my comments. Look, I'm not trying to be a bully here, and I DO think that the FSM you have created is interesting, unique, and a cool example of how user-defined aggregates can be used. The problem with it is, unfortunately, an extremely common one. If I had a nickle for every time a programmer jumped into the world of databases and came up with a "new" solution to a "never-before-seen" problem... I'd be a wealthy man. Relational databases have been around for a long time and are one of THE MOST studied and written about pieces of infrastructure/software in existence (they're interesting for so many reasons!). What this means is that it's EXTREMELY unlikely you have found a problem that hasn't already been "solved" (of course there can be wiggle room) in a theoretically correct manner. It's almost always just an individual not recognizing (or breaking down) the problem efficiently.

And that's what I am seeing here: a problem that is present and handled in LOTS of databases (I've personally done this dozens of times), but is being approached from a less-than-perfect (albeit unique) angle. I can't say that I'm "absolutely correct"... I don't have the full grasp of your domain and business requirements. I don't know precisely the degree of constraint your schema is imposing. I don't know how well communication between teams and management of your stack is handled (yes, these can be important - you did mention you had problems in these areas). Maybe yours really is the best solution - though I remain unconvinced. But I can say, that given what I know about the problem, the entity relational model, database design, and data warehousing that your solution is simply not sound. It's difficult to put that nicely. I don't mean that your wrong (apparently this is working for you). It's not black and white. Just that if one of my clients came to me with similar requirements, I would follow "the book", because this has already been written.

Here's what I'd do (SCD6):

Order [OrderId] ... [additional data]

OrderStateHistory [OrderStateId] [OrderId] [TransitionTimestamp] [PreviousStateName] [EventName] [StateName] [IsCurrent] ... [additional data]

And if you want a transitions table for your FSM to enforce explicit constraints (I don't recommend this, but it's MUCH better than hiding this data in a function/trigger):

OrderTransition [CurrentStateName] [EventName] [NextStateName]

You can figure out the keying/substitutions. Then use a simple stored procedure:

order_state_history_tr @current_state_name, @event_name -- note this the PK of OrderTransition

to facilitate transitions. This stores BOTH the transitions and the state.