I made a guide on Iksar faction for the wiki (still in progress - edit: someone already linked it gasp) that's mostly relevant to p99, including a section on friendly vendors at the beginning. It's still in progress.
Once you hit 29, you'll have invis on your shaman and can bank in FP yourself (
here's the path to the bank for Iksar, avoiding the bard guild where the GM will wreck your face if he spots you - my monk is non-KoS to NFP guards, only took 600 deathfist orc kills!).
What a lot of people will do is murder a ton of orcs/gnolls in highpass until non-KoS, then turn in scalps until they can use the banker in high keep (watch out for Ran Flamespinner behind one of the doors near the bank). The scalps have an added bonus of raising faction with corrupt qeynos guards and freeport militia.
As a shaman you might want access to Oggok or Grobb for training, but I'm not sure how to raise those particular factions.