> Clients had to generate an alternate key pair to encrypt the message, so it looked like the message was posted by some random npub.

This is the correct way to implement private messages. The relay should not use the pubkey in the signed message to test against an allow list. Private relays CAN use an NIP-42 AUTH method to authenticate the connecting user (and not the signing user) and make the allow list about the connecting user. The signed message itself must hide the real user as much as possible because it can be easily broadcasted outside of this relay. 

Needless to say that private relays that authenticate the user can track everything about the user and thus, by definition, are not very strong in privacy.