I am hoping that you could elaborate abit on your idea so as to get better advice. Will it be kind of like the concept of Dear Mr. Henshaw but with different people and as a cyoa? That would be pretty interesting to read. I suppose I offer the book I linked as a resourse, as it has the same general concept with telling a story in the form of letters back and forth.
I'm glad I could help. How little "narrative backstory" were you thinking? Perhaps it would be good to start with things you don't want in the story so you know what to avoid writing. Do you have an idea of how the reader will interact with the characters exactly? I would very much like to know more.
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.
If you're doing a strict epistolary format with written letters only, I think the plot would most likely lend itself to some kind of history/fantasy politics intrigue game. Mainly because if you set in the present day or future, you raise all kinds of questions about why aren't these people texting or emailing or calling each other on the phone. (Though you COULD tell a story in the present day using emails/texts or similar/)
I say politics for the following reasons:
Examples: Scheme for political gain, assassination plot (orchestrated by narrator, or uncovered by narrator), sending out military instructions from a distance, doing research into a mystery by getting in contact with various people, etc.
If you're not strict about "letters only," you could expand to things like scribe-written meeting notes, inventory assessments, interviews, scientific research, journals, recipes, secret codes, etc. The sky's the limit.
If you're going to do this, I strongly encourage you to take advantage of the format in some way. Don't just tell a story that happens to be told through letters. Tell a story that could ONLY be told through letters.
Narrator voice is going to be EXTREMELY important in this game. You'll need to pick someone distinct, likeable, and widely appealing to your audience. Since whole pages are going to be written in this voice, you don't really have the option of creating a bland narrator and hoping the rest of the story does the work.
Good luck! Epistolatory style can be a lot of fun.