That can happen when the message component is rendered before the message is added.
In your specific example, the bean is referenced for the first time by the <h:outputText> component and thus constructed for the first time at that moment. But the <h:outputText> component appears in your specific example after the <p:messages> component, so the <p:messages> component is already rendered and thus it’s too late to show the message.
You need to make sure somehow that the message is added before the message component is rendered. One way is using <f:viewAction>. It runs during INVOKE_APPLICATION phase which is before RENDER_RESPONSE phase. Thus it runs before any component is rendered. A perfect opportunity thus.
<f:metadata>
<f:viewAction action="#{bean.onload}" />
</f:metadata>
public void onload() {
// Add message here instead of in @PostConstruct.
}