This shouldn't be possible - as with another user you have a different Session and therefore different values for recent space/shortcuts etc. Are you sure you logged out? I'm asking because I cannot reproduce this or see any way it could occur…
Are you using the Enterprise edition with NTLM by any chance?
Anyway, i've also tried to reproduce, and i feel it is more related to the way the session is handeld.
I work with Firefox : I open a tab with webclient in it then, browse some spaces and create a shortcut. Then i open another tab with the same session, disconnect, and reconnect with another user.
Here, the message in top of Webclient GUI shows that : - in one tab i'm connected with one user - in another i'm connected with another user
But the two users have the same recent spaces and shortcuts. I have also weirdness when opening two tabs from one page : when i open two different links on two different tabs from an open session of Alfresco, the two tabs open the same link twice. That's why i think Alfresco is not really designed with firefox multi-tab in mind.