I am not at all familiar with this game so may not be able to provide the kind of help that you need, but reading over the walkthrough, it says this about the game:
If you have already exhausted all possible clues in a certain area - go to another part of the globe and then come back. New clues might surface - like the appearance of the letters here.
So, it sounds to me like if those things are not showing up for you, then it means you need to accomplish other things first in a different part of the globe, and then these items will show up for you when it's time for them to be there.
In addition to MaG's walkthrough, you might find these UHS hints helpful