Here is a description of the issue based on the attached test case:

A message is being added to the faces context in a phase listener (TestPhaseListener.java):

public void beforePhase(PhaseEvent arg0) {
logger.info("before:" + arg0.getPhaseId());
if (arg0.getPhaseId().equals(PhaseId.APPLY_REQUEST_VALUES)) {
arg0.getFacesContext().addMessage("global",new FacesMessage( FacesMessage.SEVERITY_ERROR, "error", "error"));
}

The page contains a panelTabSet that includes a nested tabSet along with ui:composition's. In the inner most ui:composition is where the message is being rendered (TabChangeTemplate.xhtml):

<ice:panelGroup id="enclosingFormData">
<ice:panelGroup>
            <ice:messages id="myMessage1" showDetail="true" showSummary="false"/>
</ice:panelGroup>
<ui:insert/>
</ice:panelGroup>
</ui:composition>

However, this configuration causes a duplicate message to be displayed under the panelTabSet. This issue can only be reproduce when clicking for the first time from the first tab to the second tab. All subsequent tab changes do not exhibit this behavior. Attached are screenshots and a test case.