The key is on the beach below, near the cliff, more towards the eastern end (I swam over before getting the battle tower, and missed it clearing Black Ring soldiers on the way by, but after getting to the end of the beach with the barrier, noticed it on my way back).
I don't think freeing the prisoner should have any influence on whether the traders lower their prices.
Welcome to the forum.
