I really hope this helps someone but the fix was a shorter password. By default, I use complex 32 character passwords. The hardware and virtual appliances only accept 31 chars. The Azure setup wizard does not limit passwords to 31 characters so I had no idea. What was happening was the management service was failing to start. After two or three failed attempts at starting, the box goes into maint mode where you can analyze the logs.
After some begging with support to let me open a case on a device that had not been registered (but I had output from the serial console with the serial number), I was put in touch with an APAC engineer who had the issue sorted pretty quickly.
I suppose this was an edge case and it would seem nobody uses long passwords except me (or they're aware of the 31 char limit which I was not)