Cannot Create Redis Cache (Premium Tier) using VNet

Question

I'm trying to create an Azure Redis Cache (Premium Tier) inside a VNet. The validation passes but the deployment fails with an internal server error.

{
"status": "Failed",
"error": {
"code": "InternalServerError",
"message": "Something went wrong.\r\nRequestID=b2ef16f8-7cd7-4290-97bf-02b74bcac556"
}
}

I created a new virtual network in the same region as the Redis cache and the azure subscription. There are no other resources using this virtual network (so no overlapping IP addresses). I've been through the troubleshooting guide here for deployment failures and couldn't find much information that resolves the issue- https://learn.microsoft.com/en-us/azure/azure-resource-manager/troubleshooting/common-deployment-errors

These are the steps I followed to create the VNet - https://learn.microsoft.com/en-us/azure/virtual-network/manage-virtual-network#create-a-virtual-network

I've also created a VNet with BastionHost and one without BastionHost and tried to use both while trying to create the Redis Cache. I retried this multiple times by changing the subnet address range for the VNet as well, but still running into the same issue.