The metadata would indeed not be encrypted, how else would the message ever arrive? if the post-man could not make out the address or the sender or if the postage was valid -- it's the same issue.
This is a genuinely interesting problem which Signal put a bunch of work into solving!
Sealed Sender lets them arrange that your recipient knows you sent the message, but they (Signal and its servers) don't - https://signal.org/blog/sealed-sender/ is their blog post about this work.
Somebody connects to Signal, and hands over a message with a recipient. Signal has an ID for the recipient (you correctly observe there's no way around that) but has no idea who sent it, only that whoever it was can prove they're allowed to send this message. They also don't know in a useful sense who the recipient actually is - you can attach a real name, a photo and so on to a profile but only your trusted contacts can decrypt that profile anyway.
It also arranges that by default Sealed Sender only works for sending messages to contacts. If you're a spammer - sending unsolicited messages to people who don't know you - your only way to send messages involves disclosing who you are to Signal, who can choose to rate limit you or block you.
Like the rest of Signal's design the sender's identity is deniable - the recipient knows everything needed to produce a fake message from anyone they communicate with and so they can't use real messages as proof to anybody else.
Because I'm a nerd I actually have the status indicators described in that blog post switched on, so I know that a few weeks later, in the middle of chatting about RDR2 one of my friends suddenly began using Sealed Sender, and other participants in that group joined in over the next few days. To a normal user nothing changed, their privacy improved significantly without them noticing at all.
Anyway, solutions like PGP leak a lot more metadata than just the sender and recipient's identities to every node along the store-and-forward route.
And the very existence of the route also leaks data.
