Session Inconsistencies IIS6

Im trying to find why my hosted server won't maintain session state.
Its not a web farm (not load balanced), its all the same server

An application requires a session to be set and then recalled (like you do
:)

However, since the server software was upgraded from IIS 5 to 6, the working
code no longer works.
(ie - login with session variables but get logged out immediately the page
changes)

Using simple code like <%=session.sessionid%> on the IIS6 server, and
refreshing the page shows a new ID most times - it should be the same id??
Testing on the old server (IIS5) would keep the same session id.

Where do I start looking and what pertinent questions do I need to ask my
host?