I guess you just never worked out of the right branches, AC. Great question!
The name seems to be about “paying” for your letter with a kiss. From online etymology: Post office first recorded 1652 as “public department in charge of letter-carrying;” Meaning “Building where postal business is carried on” is from 1657. In slang or euphemistic sense of “sexual game” it refers to a parlor game first attested early 1850s in which pretend “letters” were paid for by kisses.
Here are some cultural references from wikipedia(game):
”# A 1954 television episode of The Jack Benny Show with Fred Allen guest-starring, Benny is surprised by Allen hiding in a closet. When Benny demands to know what Allen is doing in the closet, Allen says “Playing ‘post office.’ Kiss me!”
# In his unfinished novel Answered Prayers, Truman Capote writes: “Kissing her, according to Dill, was like playing post office with a dead and rotting whale: she really did need a dentist.”
# In the 1968 movie Yours, Mine and Ours, Frank, played by Henry Fonda is on a date with a younger free-love hippie. The date is interrupted by Helen, played by Lucille Ball. While Frank and Helen commiserate over the problems they have with their respective children, the hippie says “Why don’t you drop me off at the exit, then you two can play post office!””