Про header: после старта сессии слать header location с явным указанием id сессии с пом. session_name и session_id. Работали куки - при старте сессии после headera ссылки дополняться не будут, нет - подымется стартанутая сессия (ну, автодополнение, конечно, останется). Это если нужно, чтобы без кукисов тоже работало. Если нет, -AliMamedа слушай.
Про безусловный session_start: известен минус - поисковики. Куки не принимают, все ссылки - в id\'ках сессии. Не любят они сильно этого, говорят...