И это ты делал на ssh? Я думал, что header() передаёт http-заголовок...

К тому же, я думаю, это не бага, а "фича" хостера, который не хочет нагружать свои сервера всякими ботами и т.д.
Возьми тест вдс и попробуй.