If we move to a separate encryption key (good idea) then I presume the messages are not NIP-17 giftwrap(seal(DM)) (since that specifies otherwise). And in such a case we can avoid spam by doing what Will says in the OP, which is to first require an endpoint-exchange and key-exchange through giftwraps (not 1059, something new), and if you get a giftwrap DM that is not from somebody that is already setup, you discard it. Sure it could be spam, but spammers won't have much incentive to send something that the user never sees.
Discussion
But then people can't send you messages at all unless you first manually approve them?
I guess this is also the case in MLS.
I think it has to be one way or the other. Either people can send you messages out of the blue and spam you too, or neither. Am I wrong? Is there a middle ground?
A relay that knows who is messaging you can filter out trash on your behalf, impose soft limits on the number of messages a "stranger" can send, require PoW etc.