Are you running this test with two different machines? If not, it's not a valid test. In most cases, Internet Explorer will cause a Java Application server to think that two separate browser windows on the same machine still belong to the same session. If you only have one machine to test with, you might try having one user use FireFox and another IE.
I am using Struts 1.2 and I am having the same issue. Two different users login to the same application simultaneously (on different machines). After which, we try testing it by having USER A search in one page and USER B search in another (different page) almost at the same time. The result causes either a 404 Page Not Found error in one of the user's screen, or the display in one of the user's screen to be messed up (i.e. it it mixed up with the page display of the other user).
I have no idea what is causing this problem. Is this a Struts issue?
There's so much to learn in this industry, and not everybody has the necessary interest.