"He writes with her" would only be used in English if 2 people are writing an article together or a book, etc.
'He corresponds with her' relates to the fact that he writes to her and [it is implied] she writes back. 'Correspondence' is still use to refer to the act of writing to each other, at least in a court of law!
Why not "He returns with her." ?
I thought this as well; but, it seems the literal definition is to write together?
Still have the question: Why can't you say "he returns with her." ?