Waking the Colossus Quest Won't Progress

Platform: PC
ISP: Time Warner
Type of Internet Connection: Cable
Internet Connection Speed: 300/20Mbps
Date & Time: Last 4 years
Frequency: Everyday
Character Name: Bigt
Race: Galka
World: Lakshmi
Main Job: Any
Support Job: Any
Area and Coordinates: Everywhere the quest sends me to
Party or Solo: Solo
NPC Name: Every NPC involved
Monster Name: Broken Quest
Steps:
1. Quest is registered in my current Aht Urgan quest log
2. I do not have an Imperial Missive Key Item
3. None of the city NPC's will give me their Approval Letter Key Item