Use personal letters, not letters to the realm.
As in the real world, the a well-written business letter is the path to power.
Frankly, no matter how much I like one candidate, if he makes no effort to communicate with me, and a different candidate sends me a personal message, I will be inclined to vote for the communicator. A personal message addressing my character my name and title, requesting support, asking for clarification, discussing objectives, or simply making a social call, is extremely useful.
Many players I think struggle with what to even say in such a letter. Thus, I shall offer a generic letter a new noble could send to his/her liege:
"Countess Keplerinina Lastnamia,
You have my thanks for the generous oath you have provided me, and I have acquired a unit with the revenues from my estate.
INSERT UNIT REPORT
This being accomplished, I am working in the Army of Keplerstan under Marshal Foggypants. This duty, however, leaves me some time available for other tasks. Is there any way I might be of service to you?
Sincerely,
Sir Newguy Familyname
Knight of Region A"
Establish contact. Demonstrate diligence. Ask for instructions.