You're really not gonna like the letter writing format. It really will constrain you in a lot of different ways, just like using only dialogue in your story. Dialogue, character acting and character interaction will be a lot trickier to write if you want those letters to feel natural.
I would go for a call and response approach. So you get the letter from someone and then you get a bunch of choices how to react to that letter as in a short summary of the tone. Then on the next page you have your fully written letter and the response letter of that person on the following page.
Something like this:
I stole a Serb's girlfriend and ran him over with my car. What to do?
advise him to go to the police
Tell him to hide the body
This is such a joyous event. Why didn't you tell me sooner that you ran him over. I should give you a birthday present if there wasn't a whole sea separating us two.
There should be a darn good explanation why you two are separated from each other. If the character you're writing to is in trouble, then you should have a very good reason why the player character can't just hop in and help him. I have some solutions: distance is too far to travel to here, player character has other obligations so they cannot go in person, player character is literally imprisoned, they are literally in different worlds etc.
Method of sending letters
Is it your regular mail delivery service, magic device, or big arse machine. How much info can be sent in one go and can you also send objects to help out the character you're corresponding too.
Inmates corresponding via letters to plan their escape
The lake house rip off- Romance story, but those two are separated through time or being other universes shenanigans
Professors sharing research - this can easily be a historical piece (lots of highly educated people send each other letters all the time, so I dunno, Catherine the great and a lot of other enlightened rulers have tons of penpals. It also explains the forced distance.) You can also take it the horror route (Dracula is basically a huge pile of letters and newspaper clippings and diary notes)
Just normal pen pals - you still have this kind of stuff in real life. Person you're corresponding too perhaps has a good reason why they don't wanna videocall or meet in real life. Have this as the main conflict.
Estranged family members - deadbeat father's trying to contact their children, a classic
Wartime letters - Soldiers often send letters to their family and loved ones, but also each other. Generals before the invention of radio and stuff used to send out letters all the time to their underlings (Julius Caesar did that during the Gallic wars). You can make a strategy game out of it or a heartfelt drama.
Diplomatic letters - have kingdoms negotiate stuff with each other. It can be a little dry though, but in the right hands it can be extremely engaging. It could also be about arranging a marriage between two parties, anything goes.
Spare yourself the trouble and headache and start off with two characters: the character you're writing to and the player character themselves. The more pen pals you add, the more confusing it will be for the reader and for yourself to keep track of all those storylines. So begin small.
Make sure the player character and the penpal have distinctive voices. People's writing style are very unique. No one writes the same.
why the text wall
Because I was also interested in doing such a style, so I brainstormed a bit myself.