You guys are obviously making this way too difficult.
Try leaving the faction by rebelling completely or asking the king to stop your homage. Once you are a loner, you can
make peace with a kingdom by talking to any named npc of the angry faction as long as the npc is not also mad at you.
However you will have to pay money to end the war. Once you have reset your faction relation to zero, go ask to join
the old faction once again. Your old estates will remain yours.
Simple as that. If you join another kingdom for protection, you cannot fix your relation as quickly as having your own.
Being a big man and saying sorry works. Of course, the lords themselves may still not like you, but thats what the
ladies in waiting are for. Go to a castle and talk her and pay money over and over until the lord she knows can stand to
talk to you for quests, which also make him happier.
If its your village or town that hates you, theres only one way if you are not able to enter to do quests for the
elder/guildmaster. protect caravans/farmers or check nearby taverns for a peasant that needs to rid his home of
bandits. Yes, theres a chance you will have to fight someone on the way to apologize. It happens.
Maybe we should develop a way to send messengers? Nobody shoots the messenger, right?