Got in touch with MSFT premium support.
I was using the token that I got from the Azure portal (by trapping from network call). With that token and this header, it was working.
But with the one we generate programmatically, it doesn't work since there is a limit of 4 calls per scope per minute. It was confusing because this limit is not there in Azure portal token, but that's understandable considering Azure won't keep a limit for its own portal.