That's what's supposed to happen because the w3c validator doesn't accept cookies. If PHP sees that it can't detect its session cookie when "start_session" is called, it will tag the URL with the session ID request variable. It should not have any effect on the validator unless your script depends on cookies somehow and will spit out invalid HTML code as a result of the missing cookie/session info.
I myself use a combination of the "get_browser()" function (which requires an externally available php_browscap.ini file and a mofication to your site's php.ini file) along with a page reload to detect cookie/session handling availability. It's tricky but not un-doable and it handles pretty much everything except for people that have their browsers set un uber-anal-retentive mode.