@gwer если написать просто header("Location: $new_link"); то код будет 404. Не помню эту строку в вашем примере header("HTTP/1.1 301 Moved Permanently"); когда оставлял комментарий.
Лучше конечно делать проверки на стороне сервера, чем на пхп, но в данном случаи вариант с 404 страницей на мой взгляд лучше.
Только нужно не забывать, что 404 отдается на правильном сервере с 404 кодом, а дальнейший редирет выглядит странно, не уверен как это поймут роботы.
header("Location: $new_link");
то код будет 404. Не помню эту строку в вашем примереheader("HTTP/1.1 301 Moved Permanently");
когда оставлял комментарий.