T2 Mac with empty internal storage won't boot from install USB
I did eventually get Internet Recovery working. I was getting various errors (-1008F, -2106F and perhaps others) after long periods of time spent waiting for the boot to complete. While some of these may have been down to a shoddy internet connection, it seemed as if it would just error immediately after the bar had reached 100%.
After doing a bit of digging I removed the Mac from my iCloud account via appleid.apple.com as well as perform all steps on this guide to restore a Mac with Apple Configurator 2 (I found about that on this thread). You will need an additional Mac on hand to do the latter.
After doing that, then booting with Internet Recovery and then reinstalling from the recovery menu I still needed to log in using my iCloud credentials as well as my old local account. Fortunately for me that wasn't a problem at all, but bare that in mind if anyone reading is in a similar situation!