Depending on the difficulty level, the harbour cove gate key could have been on a bench (IIRC) to the right of the gate, or past the gate (so you have to use Telekinesis, the teleporter pyramids or a teleport spell to get it).
Pontius drops a key for a different gate.
