It turned out, near the end of the second session of my open gaming table, that the healer had actually solved the substitution cipher bounty I had provided!
The duskblade's player facepalmed about ten times in a row because the bounty turned out to be one long reference to the previous campaign, and to his last character (the elf wizard) in particular.
I gave the healer a bunch of extra experience for solving the puzzle, tempered with a slight penalty for doing it at the expense of paying attention to the goings-on of the game. Although I'm not sure what I expected - maybe for people to work on it before the game starts and after it finishes? But at least he was playing his character well - figuring out this puzzle was much more interesting to the character than anything else. Though why he took it to the mine with him rather than just solve it at the adventurer's guild, I don't know. High intelligence, low wisdom, I guess.
Incidentally, the substitution cipher I actually used was in fact the Standard Galactic alphabet. Incidentally, this is an instance where I halfheartedly, and with a modicum of success, adhered to the Three Clue Rule, which says that "For any conclusion you want the PCs to make, include at least three clues." Or, more loosely, provide at least three different ways to get to any given plot point.
I allowed for at least three ways to solve the cipher (with the possibility of more if the players had been clever enough):
1.) Brute force it the old-fashioned way (using observations like: "e" is the most common letter; "the" is the most common three-letter word; "a" and "I" are the only possible one-letter words; etc.) This was how the player wound up doing it.
2.) Roll well enough on your Decipher Script check that I give you some free letters, which makes (1) substantially easier.
3.) Have played enough Commander Keen that you recognize it as the Standard Galactic Alphabet, and consult the wikipedia page or other places that give the complete alphabet.
I can think of at least one other thing that could have partially helped, involving being familiar enough with the story to fill in gaps. (It involved a +1 Frost Dagger that the wizard had taken from the body of the High Priest of Vecna, then loaned to the swashbuckler/knight, then the vampire Baron Rogan took it off the swashbuckler/knight's body, then King Terek II had inherited it from him, and it's currently in the royal treasury and some relative of its original owner wants it back.)