Если разница между наличием или отсутствием заголовка зависит от того, был ли подключён файл bitrix/header.php или не был - то логичнее всего проверить содержимое этого файла, что там происходит.
Вангую, в этом файле происходит вывод данных (намеренно или случайно из-за попавшего в файл непечатного символа), из-за этого последующие вызовы header завершаются с ошибкой, но ошибки выводятся в лог, а не в браузер. Почему при этом на другом сервере всё работало - например, из-за output_buffering, который консолидирует выводимые данные порциями определённого размера и разрешает устанавливать заголовки, если фактического вывода в браузер ещё не произошло к тому моменту.
Но это только догадки, для более точной информации - для начала ознакомьтесь с логами ошибок.