How to pass a message using template_redirect

You could approach the problem from the other side and look up the post based on the HTTP_REFERER, available in the $_SERVER superglobal:

http://php.net/manual/en/reserved.variables.server.php

You could perform a lookup of the page based on the URL of $_SERVER['HTTP_REFERER'] and get post information that way. You can also keep your 301s cleaner by not adding referrer query vars, and put the 301s in the .htaccess or Apache config as one-liners:

RedirectPermanent /old-path /new-path