AzureFirewallをデプロイするには、関連付けるネットワークのサブネットに
・AzureFirewallSubnet
という名前のサブネットを用意する必要がありますが、もう一点盲点になりやすい部分があります。
既存のファイアウォールポリシーを流用する場合は
・”DNATルール”
を確認してください
作成するファイアウォールに関連付けられない宛先IPが入っている場合デプロイに失敗します。

こちらのエラーはInternalServerErrorとしか表示されずトラブルシューティングが困難ですので
作成前にご確認ください。
