In response to the solution posted in the comment below, there are some practical issues with this solution that must be kept in mind and handled by your code. I developed an application using a similar "use-it-once" key to manage sessions and it worked great but we got some complaints about legitimate users getting logged out without reasons. Turns out the problem was not tentative highjacking, it was either:
A- Users double click on links or make 2 clicks very fast. The same key is sent for the 2 clicks because the new key from the first click didn't get to the browser on time for the second one but the session on the server did trash the key for the new one. Thus, the second click causes a termination of the session. (install the LiveHttpHeaders extension on firefox and look at the headers sent when you click twice very fast, you'll see the same cookie sent on both and the new cookie getting back from the server too late).
B- For any given reason, the server experiences a slow down and the response with the new key (which has replaced the old one on the server) is not returned to the browser fast enough. The user gets tired of waiting and clicks somewhere else. He gets logged out because this second click send the old key which won't match the one you have on your server.
Our solution was to set up a grace period where the old key was still valid (the current key and the previous key were both kept at all times, we used 15 seconds as a grace period where the old key could still be used). This has the drawback of increasing the window of time for a person to highjack the session but if you tie the validity of the old key to an IP address and/or user agent string, you still get pretty good session security with very very few undesired session termination.