Eu tive este problema algum tempo atrás e resolvi utilizando a ultima solução apontada no artigo que você citou (http://ocpsoft.org/java/persist-and-pass-facesmessages-over-page-redirects/).
Comigo funcionou com aqueles 2 passos, você chegou a tentar com ele?
Consegui resolver. A unica coisa que eu alterei foi a forma de apresentar a mensagem. Antes eu tentava apresentar a mensagem passando o ID do formulário e o ID do <p:mesages> agora não, eu crio uma String com a mensagem e depois so passo ela no context.addMessage(null, new FacesMessage(FacesMessage.SEVERITY_INFO, message, message));