I figured this out. I replaced my search pattern with:
"(XXXXXXX)([!®])"

and my replacement pattern with:
"\1®\2"


My mistake was I was reading the search as 'XXXXXX not followed by a ®", where it was really "'XXXXXX followed by any character except ®", and that character was part of the found string.