会话ID太长或包含非法字符

I've got a problem on a site where sometimes there is logged an warning like:

session_start() [<a href='0function.session-start0'>function.session-start0</a>]: The session id is too long or contains illegal characters, valid characters are a-z, A-Z, 0-9 and '-,'

I went further and dumped the $_SERVER variable:

[HTTP_COOKIE] => name2=; name1=; my_session=; __gads=; __utma=; __utmc=; __utmz=

The requests are coming all over the world, they are not many, 1-2 per day which comes in this format ( I mean all cookies seam to be empty? ).

Any clue in what conditions and why is this happening ? An how this should be handled ? session_regenerate_id() does nothing I still get the same warning