This is dependent on certain configuration options, namely "use_only_cookies" vs. "use_trans.sid" (something like that) in php.ini.
PHP generally sets a cookie with the session id number on the client. In the event you have a client not accepting cookies and "use only cookies" set, you could very easily have this type of problem.
With "trans" (-parent) session handling, if cookies fail, then PHP will automagically append the SID to the query string, IIRC.
What's phpinfo() tell you about your session settings?