Second vote for lacquer thinner to potentially dissolve the Permalyn and suck it out of the wood. Perhaps try the stripper first, then lacquer thinner second - it's a combination of all the nastiest solvents available.
If neither of the above suck the finish out of the wood, you may try adding some aniline dye to some lacquer thinner, then rubbing that in to see if it takes (try on some scrap first)? It may dissolve enough of the sealer to get the dye into the wood, then the solvent will dissipate and you could then stain the rest of the rifle as you want.
If all else fails, stain the rest of the gun as you will, then try different shades of brown and black sharpie to get the carving - maybe go for an aged look with your finish. Best of luck, please let us know what you try.
-Eric