I would say that it's even more likely than you might initially suspect. Some large organisations, such as AOL, have been known to send all of their traffic through just a handful of gateways. I've run into this problem a few times.

Typically, as Masem suggests, I add in some sort of random value, and as precise a time value as I care to conjure up, just to even out the randomness a bit. Also, if the script runs on several machines behind a load balancer, I'll use an unique identifier of the machine (host id on Sun, for example) to limit my collision space further. Be creative, but be wary of this problem.

In addition, the less formulaic the data is that you encrypt, the less likely someone will be able to hijack the session by computing what another user's session identifier is.