Not sure what's happening, but a workaround is to go to a URL like https://wa.me/+1234567890 (use the full international number including country code) in the browser, which will then ask to open the number in WhatsApp. You can then send the person a message which will mean they're in your recent messages list and you can chat/call them from there.
This works even if you allow WA no contacts permission at all, so you don't need to allow them any access. It does list them by number rather than name though - for that it needs contacts permission, although you can use Contact Scopes so it can only see those contacts you allow it to.