Have you cleared down the mountain path at the start of the fjords, as well as the beaches, depleted ore mine, the path to the harbour and High Halls, etc? After that you could start on the flying fortresses (Stone's would be easiest).
With your battle tower runners fully upgraded (talk to your trainer and enchanter), you shouldn't have any problems getting gold or potions. Send the herb runner for ginseng (or whatever else you need for the strongest healing potion you can make) and the other two for malachite ore and diamonds to sell; as soon as they leave the tower just teleport out and then back and they will have returned (usually successfully).