There's a kingdom that I have -32 relations with, but there's literally no way for me to improve this.
No lord in the kingdom will give me a quest, and I can't pay my way out of it because we aren't at war.
I've been helping them win sieges, win battles, and I've been doing quests for people...