The simple answer is that the problem (and message) can be avoided by correctly using RuleDelayed (:>) rather than Rule (->) in your string replacement, preventing the evaluation of StringMatchQ before the string is substituted into it.

I believe the lack of a message on the second execution is explained by the caching or limiting of infinite evaluation that Mathematica uses. This is a subject that I do not have a good understanding of there I cannot provide any true explanation, only observations; take any declarative statements as opinion only.

Consider the Trace output of this:

f = {head[3, "+"], Pi} &; f[] // TracePrint 

f[]
f
{head[3,+],[Pi]}&
({head[3,+],[Pi]}&)[]
{head[3,+],[Pi]}
List
head[3,+]
head
3
+
[Pi]

And a second evaluation:

f[]
f
{head[3,+],[Pi]}&
({head[3,+],[Pi]}&)[]
{head[3,+],[Pi]}

At least in some circumstances an expression that is comprised solely of sub-expressions that do not evaluate appears to be marked as not needing evaluation if it is seen again.

This behavior can be seen in a Trace of your question code, or in this condensed example:

x=. g[s_String] := StringMatchQ[x, "+"] g["string"]; g["string"] // TracePrint 

g[string]

g

string

StringMatchQ[x,+]

Notice that the second time g["string"] is evaluated the expression StringMatchQ[x,+] is never actually evaluated; its components do not appear in the Trace. Compare this behavior to the same code with a subexpression that will always evaluate:

h[s_String] := StringMatchQ[2 + 2, "+"] h["string"]; h["string"] // TracePrint 

h[string]
h
string
StringMatchQ[2+2,+]
StringMatchQ
2+2
Plus
2
2
4
+
StringMatchQ[4,+]
Message[StringMatchQ::strse,1,StringMatchQ[4,+]]
(* remainder trimmed *)

The h function issues the message every time it is run because, due to the presence of 2 + 2, it is never marked as not needing evaluation.

The simple answer is that the problem (and message) can be avoided by correctly using RuleDelayed (:>) rather than Rule (->) in your string replacement, preventing the evaluation of StringMatchQ before the string is substituted into it.

I believe the lack of a message on the second execution is explained by the caching or limiting of infinite evaluation that Mathematica uses. This is a subject that I do not have a good understanding of therefore I cannot provide any true explanation, only observations; take any declarative statements as opinion only.

Consider the Trace output of this:

f = {head[3, "+"], Pi} &; f[] // TracePrint 

f[]
f
{head[3,+],[Pi]}&
({head[3,+],[Pi]}&)[]
{head[3,+],[Pi]}
List
head[3,+]
head
3
+
[Pi]

And a second evaluation:

f[]
f
{head[3,+],[Pi]}&
({head[3,+],[Pi]}&)[]
{head[3,+],[Pi]}

At least in some circumstances an expression that is comprised solely of sub-expressions that do not evaluate appears to be marked as not needing evaluation if it is seen again.

This behavior can be seen in a Trace of your question code, or in this condensed example:

x=. g[s_String] := StringMatchQ[x, "+"] g["string"]; g["string"] // TracePrint 

g[string]

g

string

StringMatchQ[x,+]

Notice that the second time g["string"] is evaluated the expression StringMatchQ[x,+] is never actually evaluated; its components do not appear in the Trace. Compare this behavior to the same code with a subexpression that will always evaluate:

h[s_String] := StringMatchQ[2 + 2, "+"] h["string"]; h["string"] // TracePrint 

h[string]
h
string
StringMatchQ[2+2,+]
StringMatchQ
2+2
Plus
2
2
4
+
StringMatchQ[4,+]
Message[StringMatchQ::strse,1,StringMatchQ[4,+]]
(* remainder trimmed *)

The h function issues the message every time it is run because, due to the presence of 2 + 2, it is never marked as not needing evaluation.