Do you have the battle tower yet? If so, talk to your trainer and enchanter to upgrade your runners' equipment, to give them a better chance of being successful. Also, once fully upgraded they will get back faster; you just have to wait until they are out of the tower, and then teleport out and back again. If you take the teleporter to the exterior sentinel island teleporter shrine, you can use the dragon stone to teleport to the throne room and leave repeatedly to build up ingredients (for the strongest healing potion you can make, etc).
If you don't have enough gold to upgrade everyone, start with the gem runner and send him out for diamonds to sell, so you can upgrade the other two (the ore runner can fetch malachite ore, but they are not as valuable as diamonds).