>>Is there some simple solution how to avoid this?
Don't write session ID's in the url. :)
A solution where the session ID is stored in a cookie works much better.
The other option would be to check IP addresses before writing the session ID's to the URL. If a search engine IP is detected, the server simply serves the page without the ID. All IP's not on your list get the unique ID.
Don't think of it as cloaking. I can't imagine any search engine (even the anti-cloaking zealot, Google)having any problem with that approach. You are delivering the same page to both spider and human. You would be doing them a big favor.
You could probably even handle it just using the UA.