Y .. que configuración de PHP sobre sesiones usas?
Al parecer usas:
session.use_trans_sid = 1 .. lo que provoca que los links se incrustre el SID ..
Pero también usas:
session.use_cookies = 1 .. lo que provoca que el SID se siga propagando en cookeis.
Las cookeis no quedan disponibles hasta la próxima petición al servidor .. Por eso deduzco que es normal lo que te sucede:
Entras a tu sitio (primera inciación de tu session_Start() .. PHP sobre-escribe tus links .. y la cookie con el SID se manda al cliente .. en la proxima recarga de página (o salto a otra página de tu sitio) = petición al servidor .. EL SID ya está en la cookie . .así que PHP lo sigue usando de la cookie y no sobreescribe más el URL con el SID.
Si quieres propagar el SID en cookeis .. no uses session.use_trans_sid = 1 .. usalo a 0 .. pero ten cuidado .. por qué PHP no sobreescribe todo tag o funcion para redireccionar automáticamente . ejemplo: no lo hace en <meta de refresh> ni en javacript (window.open .. window.location.. etc) ni en PHP con su header("Location: ....") .. En esos puntos concretos por lo menos tendrás que propagar el SID de forma manual.
Mas info en
www.php.net/session (hay que leerlo!)
Un saludo,