Sessions and search spiders

Some of our webapps create a session for every visitor, which is  
rather a common thing I would say. This works more or less fine when  
the page content does not have to be indexed by search spiders:  
Simply mark the pages as noindex, nofollow and block the IP# of the  
spiders that do not respect these instructions.

But how do you deal with the situation where the pages _should_ be  
indexed? Here, the search spiders are creating new sessions until the  
app goes down when they revisit old links (containing old session  
ids). What is the correct way to handle this?

Thanks!

Will