Update and final conlusion
It turns out that the spec actually says that this is the desired behavior, therefore IE9's implementation is broken.
4.2 The sessionStorage attribute
When the setItem(), removeItem(), and clear() methods are called on a Storage object x ... if the methods did something, then in every HTMLDocument ... [that is] associated with the same storage area, other than x, a storage event must be fired....
So as we can see, the spec does do a really bad job at making it clear, that this is the specified behavior. That was the reason why Opera 10's implementation was broken and it's most likely also the reason why IE9's implementation is broken.
What do we learn from that? Always read every, single, word of the specification (especially if you're implementing the stuff...).
Old answer
As you said the basic behavior here is "Invoke on all but the current page".
There's an old Chrome Bug Report from last July.
As one can read there, Firefox has the same "issue". I've tested this with the latest nightly, still behaves the same way like in Chrome.
Another test in Opera 11 shows that this must be some kind spec'ed behavior, since Opera 11 does the exact same thing but Opera 10 did fire events on all windows / tabs. Sadly the official changelogs for Opera 11 do not state any change for this behavior.
Reading through the specification, nothing there states this behavior. The only thing I could find is:
The storage event is fired when a storage area changes, as described in the previous two sections (for session storage, for local storage).
When this happens, the user agent must queue a task to fire an event with the name storage, which does not bubble and is not cancelable, and which uses the StorageEvent interface, at each Window object whose Document object has a Storage object that is affected.
Note: This includes Document objects that are not fully active, but events fired on those are ignored by the event loop until the Document becomes fully active again.
Well, what does the Note mean?
From another specification:
A Document is said to be fully active when it is the active document of its browsing context, and either its browsing context is a top-level browsing context, or the Document through which that browsing context is nested is itself fully active.
Doesn't make sense? Yes. Does it help us in any way? No.
So we (in the JavaScript Chatroom) poked on #whatwg to see what all of this is about, so far there has been no response. I'll update my answer as soon as we get any response.
To conclude for now
Firefox, Chrome, Safari and Opera have the exact same behavior. That is, they do not fire on the tab / window that made the chance to localStorage.
But IE9 Beta behaves like Opera 10, so it fires on all tabs / windows.
Since the author of the localStorage spec works at Google in R&D, I hardly doubt Chrome would get this wrong. And since there are no Bugs on this over at Bugzilla and Opera changed the behavior in 11, it seems that this is the way it should work. Still no answer why it works this way and why IE9 behaves differently, but we're still waiting for a response from #whatwg.