If you are a merc and catch a party, don't release them, donate them to a dungeon. Damn if you catch someone who is the worst enemy of the clan who rules the town, you donate the prisoner, you can get 42 relation with them(with high charm) . Make that with every kingdom and your relation problem at the start of your own kingdom is solved. Releasing a lord after battle is capped at 6 I believe? Also give clans influence is cappped at 2(lol). So donating lords to other clan fiefs and prison breaks are the best method to build up relation. Than its only a money issue.