[SOLVED] In which order `storage` event is received?

As already quoted in the previous answer, the specs say

This specification does not define the interaction with other agent clusters in a multiprocess user agent, and authors are encouraged to assume that there is no locking mechanism.

Then, each Document will have its own Storage object set as its local storage holder.
This Storage object is supposed to be a wrapper around a storage proxy map which itself should act directly over its backing map which is supposed to be directly the storage bottle's map, i.e. where the data is actually stored, and thus this should be the same for all Documents.

So... that doesn't help much to know what should happen in case two same-origin Documents in two different agent clusters (and thus possibly running in parallel) would write to the same bucket at the same time.

All the specs say is that as an author you should not expect any locking mechanism.

So in your scenario, according to the specs,

Can 2 be stored before 1?

It's a definitive no. setItem() updates the map synchronously there is no way 2 would be set before 1 from the same agent.

Can 3 or 4 be stored between 1 and 2?

Yes it can. If your tab_1 is locked between these two lines there is nothing in the specs that prevents tab_2 from writing to the same map.

Can tab_3 receive storage events not in same order as values were stored in?

setItem() is responsible of broadcasting the storage, which will queue a task on every global object whose Document's Storage's map will point to the same bottle's map, and in order to queue that task, it must use the one and only DOM manipulation task source, so it's ensured that all the events will be fired in the order their respective tasks have been queued.

Now as to what implementations actually do, it seems a bit complex.

To test this, we need to have same-origin documents running in parallel. The best for it is to open separate browser windows (not just tabs) and navigate through a common origin from there. Then we can try to write to tab_1's Storage, and begin a busy loop that will read the same key that it just set. While tab_1 is performing its busy loop, we can ask tab_2 to also write to the same key as tab_1 did. All this while listening to storage event in a tab_3. If they were really updating the same map, we'd see the change during the busy loop in tab_1, or tab_2 would have to somehow wait until tab_1 is done with its busy loop.

I prepared these page tests:

tab_1,
tab_2,
and tab_3.

Please make sure they all run in their own agent cluster by checking that tab_2's content is updated even while tab_1 is busy (red background).

tab_1

document.querySelector("button").onclick = async (evt) => {
  document.body.style.backgroundColor = "red"; // Make it visible when the page is locked
  log("begin test");
  await new Promise((res) => setTimeout(res, 10));
  localStorage.test = "1";
  let a = localStorage.test;
  const t1 = performance.now();
  while(performance.now() - t1 < 3000) {
    if (a !== localStorage.test) { // Check whether the value has changed
      log("value changed during busy loop");
      a = localStorage.test;
    }
  }
  localStorage.test = "2";
  log("end test " + localStorage.test);
  document.body.style.backgroundColor = null;
};
onstorage = ({ newValue, key }) => {
  log("received a new storage event");
  const currentValue = localStorage.getItem(key);
  log({ newValue, currentValue, key });
}

tab_2

document.querySelector("button").onclick = async (evt) => {
  log("setting values");
  localStorage.test = "3";
  localStorage.test = "4";
  log("values set " + localStorage.test);
};

tab_3

onstorage = ({ newValue, key, url }) => {
  log("received a new storage event");
  const currentValue = localStorage.getItem(key);
  log({ newValue, currentValue, key, url });
}

The actual results are a bit surprising. In Chrome we can see in tab_3 that it received the first event from tab_1, then the 2 events from tab_2, and the last event from tab_1 (1, 3, 4, 2). So this confirms the fact that 3 and 4 can be written in between 1 and 2. The surprising part is that tab_1 didn't see the value change at all during its busy loop.
This would mean they don't actually update the main bottle's map, but just the wrapper or a local version of the map, and somehow wait on something to update the actual map or every local versions, even though this isn't in accordance with the specs. And while tab_1 also receives the events from tab_2, in the next tasks, the stored value at the time it receives the event is actually 2 and not 4 like the event's newValue says it is.

In Firefox the behavior is yet a bit farther from the specs since they do apparently broadcast the storage only at the end of the task. So there in tab_3, we actually receive the two events from tab_2, and then the two events from tab_1 (3, 4, 1, 2).
So the answer to your third question is actually also a yes...