Is this puzzle on the critical path? That makes a big difference. If it's not on the critical path, you can let it be. Some players will solve it, others won't.
Hmm... That's a good point. The instance of this puzzle that brought me here isn't on the critical path, but I do have it in mind to have other instances of it on the critical path later in the game, I believe.
In any case, if the puzzle is quite so hard then I fear that the fairly slight reward for this instance won't be worth it--it really was intended to be a quick-and-easy instance of the puzzle. :/
If you want to push the player towards a solution but not in any way reveal letters, note that players will be biased towards assuming that letters with ascenders and descenders will represent consonants, and that some but maybe not all of the rounder characters will be vowels. You can use this to your player's advantage to make things easier. Like if your initial word was along the lines of ???? players would have an initial bias towards words with a CVVC structure rather than words with a VCCV structure.
Ooh, that's interesting! I didn't know about that--thank you! ^_^
You can perhaps also give a purpose to decrypting. "It leads to great treasure in the mountains" would then suggest to try "money", "path", "rock", "left"/"right", "steps", "meters" or "feet".
Hum... That's perhaps a bit awkward in this situation: The puzzles don't appear in a vacuum, but rather are encountered while exploring an environment. As the environments in question are generally desolate ruins and the like, it seems a little out of place to have something handing out clues like that.
I might try providing a key-word along with the puzzle, but not filled in, or perhaps even rethinking this puzzle entirely...