I'm finally able to install WhatsApp back. As suspected, the issue is not GrapheneOS/Play Store, but WhatsApp's stupid spam engine mis-classifying WhatsApp users on GrapheneOS as spam and permanently blocking the number.
The only trick that worked is to delete the WhatsApp account (from another Google certified phone) and creating the account back on GrapheneOS after a minimum of 90 days. The 90 days interval is because WhatsApp permanently deletes the account from their servers and probably the spam status as well.
When you install WhatsApp back after 90 days, remember the following
- Ensure Play Store and Play Services are installed
- Allow "Dynamic code loading via memory"
- Allow "Dynamic code loading via storage"
- Allow "Native code debugging"
- Allow Google Play Integrity API usage
- And other casual permissions like Contacts, Phone etc.
I have installed it on my main profile and hence I don't know how it'll function on a different profile. Another thing is, do not immediately mesage others as soon as you install. Leave sometime for the cooling, before you regularly send messages to other users.
WhatsApp is an app that DOES NOT respect user's privacy or their rights. For me, in my country, I cannot participate in the society without WhatsApp and hence I'm okay with enabling these permissions. Your situation may be different. But if you wish to use WhatsApp, you've to relax your hardening to allow WhatsApp to think you're a normal user. I hope this solution works for you.