Location of Spy Letters:

Letter 1: Mencar Pebblecrusher (AR0712)
Letter 2: Koshi (AR0907) - Guarded Compound
Letter 3: Zorl (AR0701) - Sewers under Temple
Letter 4: Beastmaster (AR0406) - Copper Coronet
Letters 5-6: Captain Dennis (AR0514) - Delosar's Inn
Letter 7 - Fitz (AR0404) - Sewers under Copper Coronet

Collect letters 1-4 and 7, the latter will tell you where to look for Captain Dennis.