Are there any external URL links to your site that may have a session ID appended to them? It could be that some visitors are coming in on a previously allocated session number... I'm not sure about this, but it's unlikely a browser will cause this.

Test the shop by using different machines to create new TEST customer accounts, then go through the motions - as would a normal customer. See if this duplicates the behaviour.