Depending on the cultural details of your game world, you can sometimes use languages this way. Why would this ostensible merchant have a primer on Infernal?
Or loot/gear that is linked to other plot elements. A group of bandits, for example, may be armed with high quality weapons. (I used that in a recent game... the PCs were immediately curious and took some of the weapons to a nearby city, eventually finding the blacksmith who made them and thus eventually connecting the bandits to a local lord who was encouraging them to prey on one of his enemies.) That's also a cliché, really, but it was more interesting than a letter from the lord in the chief's pocket.
Other quick ideas:
- Coins stamped with the seal of another kingdom.
- Trade goods from an exotic region.
- Something marked with a crest or coat of arms. (History check to figure out what it represents.)
- A map to a rendezvous location.
- A palantír, magic mirror, or other magical communication device. The PCs might try to trick the mastermind into believing that they represent the former lieutenant; the mastermind may be duped or play along to trick them later. Or he may just hang up on them, leaving them with a mystery to solve. Etc.
- A receipt for a large deposit of funds into a mysterious account. (Fantasy Swiss Bank).
- Evidence of blackmail.