A few stabs in the dark...
Is the client using pipelining to make multiple requests before it gets a response to the preceding requests? Can you disable HTTP 1.1 on the browser and still reproduce the issue? If disabling HTTP 1.1 on the browser resolves the issue, you could try using a rule to set the version to HTTP 1.0 for all requests that don't already have a UIE persistence record.
Edit: on second thought, why not just use cookie insert persistence rather than trying to persist off of the app's session ID in the ASPSESSIONID cookie?
Aaron