Couldn't you have an npub just for the notifications, you then giftwrap to that npub and further giftwrap to the user's npub.

That way you don't know who the notification is actually for (its gift wrapped to a unique npub that's only used for that), and then it's further wrapped to the user, so you don't need auth nor trust from relays, it can be pushed to any public relay