Make sure your <h:outputText> is outside the form that contains the <a4j:commandLink> or else it will bind the value of the outputText with the actual value in the form, leading to odd behavior in your page.
<h:form>
<a4j:commandLink value="somevalue" id="someid" action="#{MyBean.myAction()}"
reRender="outputtextid">
<f:param name="paramid" value="paramvalue"/>
</a4j:commandLink>
</h:form>
<h:outputText value="#{MyBean.outputValue}" id="outputtextid" />
If you must have the <h:outputText> inside the form, you should consider updating the value using the oncomplete tag attribute in the commandLink that executes JavaScript code.
In case you want to show a message to the user, you can use <h:messages> or <rich:messages> tag component, this will be a better option than using an outputText.