just another idea:

try to find all wildcards plus leading and following characters

/(.)x(.)/

so every real match must be of a form preceeded by 1..$1 and $2..6 in this special case.

Since you have arbitrary characters w/o real order you will need to precompile a look-up hash to find the patterns needed for $1 and $2.

e.g. 12a34a56 would lead to $pre{a}=qx/12a(34a)?/ and $post{a}=qx/(a34)?a56/ or better $post{a}=qx/(a34|a34a56)/!

the check of the hashes can be done in a while loop against $PREMATCH and $POSTMATCH or in embeded perlcode with something like (?{..})

No guaranties, I'm typing mobile and can't test ATM.

But this should be quite efficient, even for cases where x is a wildcard for more than 2 characters.