Specifically, there's a building type that is long and rectangular and almost totally open on the sides, in which multiple shops will be set up. All of them have treasure chests in them, so you should be pretty familiar with the layout if you've been nabbing chests. There's several of these in the docks area to the East, but in the West, there's only one that I recall, which is mostly centered North-South. It's on the main North-South road on the western half of the city. There's a ton of soldiers specifically guarding it, and you will be instant-aggro'ed if you walk into it.
Just walk up to the West side of the building and look for where the chest is/was. There should be a guard dog nearby, regardless of whether you've looted the chest. Just drop some bait an you should get credit.