Is it possible to recycle IIS application pools without losing user sessions?

In-memory session state is stored in the memory of the IIS worker process. When you restart the application pool you are effectively stopping and restarting the worker process, so whatever state is held by the worker process, including all session objects, is lost. So, yes, you need store session data outside the IIS worker process, such as in SQL, in order to not "destroy" users' session data.