Definetly only way to prove fact of being truly mercs is to begin from work contract with former enemies.
I think moment later some other clan will pay with real silver or gold, not stones. To fill roster, aslike clanless traders, for with most teryfing moment at strat is being attacked by any clan (no chance to make real roster). As long mercs won't like to keep too many land for themselves idea should work nice.