If you are using a ReplaceHandler, you can actually put the handlingInstanceID in your custom error message:
<exceptionHandling>
<exceptionPolicies>
<add name="ReplacingException">
<exceptionTypes>
<add name="Exception" type="System.Exception, mscorlib, Version=2.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089"
postHandlingAction="ThrowNewException">
<exceptionHandlers>
<add name="Replace Handler" type="Microsoft.Practices.EnterpriseLibrary.ExceptionHandling.ReplaceHandler, Microsoft.Practices.EnterpriseLibrary.ExceptionHandling"
exceptionMessage="An application error occurred and has been logged with error code: {handlingInstanceID}"
exceptionMessageResourceName="" exceptionMessageResourceType=""
replaceExceptionType="System.Exception, mscorlib, Version=2.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089" />
</exceptionHandlers>
</add>
</exceptionTypes>
</add>
</exceptionPolicies>
</exceptionHandling>