Definitivamente tienes un problema con la propagación del SID.
Tu configuración de PHP usa la propagación del SID en cookies. Las cookies al parecer no se están generando correctamente.
Podrías hacer la prueba de propaga el SID manualmene en el URL. En tu ejemplo demo de sesiones que usas un formulario HTML, propga el SID en un campo oculto:
Código PHP:
<input type="hidden" name="<? echo session_name() ?>" value="<? echo session_id() ?>">
Si así te funciona, tendrías que propagar el SID en el URL en todo redireccionamiento que hagas, links y demás "manualmente" o intentar forzar la configuración de PHP vía función ini_set() o por un .htaccess (si tu proveedor te lo permite usar).
Por otro lado, deberías ver que pasa con la "cookie" por qué no se genera. La cookie que PHP genera como toda cookie se puede configurar ciertos parámetros como el "domino" al que pertenece o el directorio para su ambito entre otras cosas. Para alterar esos valores de la cookie que PHP crea puedes usar:
session_set_cookie_params()
www.php.net/session_set_cookie_params
Un saludo,