Я думаю, что единственный полезный вариант - использовать куки.
Когда запрашивается URL с неправильным слагом, установите cookie для этого URL без слага:
$path = substr($_SERVER['REQUEST_URI'], 0, strrpos($_SERVER['REQUEST_URI'], '/')+1);
setcookie('wrong-slug', 1, 0, $path);
Затем проверьте, существует ли такой файл cookie, и отобразите ваше сообщение:
if (isset($_COOKIE['wrong-slug'])) {
echo 'The location of this resource has changed. Please update your bookmarks.';
}