A number of the users were sitting behind a nat router and thus appeared to the application as the same ip (many of you are probably already chuckling).

It's not a laughable mistake, it has been made before. This form of NAT (Overloading or PAT - Port Address Translation) has been around for quite sometime now, I don't see why this potential snag was picked up much earlier (during the design phase).

Even though multiple clients behind a Port Translating Router appear to have the same IP address, each HTTP connection is established from a unique source port on the PAT router and perhaps this could be used to your advantage. Maybe it helps to put an IP address + Port Number combination like 172.16.0.1:2048 (Or, even better, if you are using IO::Socket (or similar), the socket structure) in the penalty box?

On the other hand, maybe that isn't such a good idea. Not all browsers reuse an existing source port (and therefore the router doesn't necessarily use the same ports either) especially if the server doesn't send out/doesn't need to send out frequent keep-alives.

Using a hash taken from multiple values such as client's IP address, initial port number, client's local time, client's user name, a new value from your ID pool, the server's local time, etc stored in a session cookie seems like a good solution. The more context-sensitive values you use, the harder it is to determine the session ID, especially if your session-ID algorithm is unknown to the users and the hash is a secure, tested one-way digest like SHA1 or SHA256.

Having said that, It is still not completely impossible to determine and forge session-IDs but if a session ID is generated anew after a user is authenticated (via password or other means) a hacker really has little chance in getting aroud session IDs. A hacker might compromise a user's password and bypass session ID security, but that is a whole different issue. Yes, you really ought to use session cookies if you wish this information to persist.

Session IDs should not really be considered a security measure, only as a means for identifying a particular session - DO NOT use the session ID as a form of authentication under any circumstances, you must always rely on the user's credentials for that.

update: My 2 cents on what constitutes a session after Washizu pointed out the potentially user-frustrating timeout problem.

If you are really worried about security and your application demands it, HTTPS addresses your concerns.