Wow, thank you for the insight, AllegedBanana! That is very helpful :)
Azure support got back to me and it sounds in line with what you are saying regarding ICMP.
There is a tool called PsPing that can circumvent that.
ScienceDiscoverer, the first thing Azure support requested was for you to try using PsPing to reach the MageQuit matchmaking server. Would you be willing to try this?
There are instructions for it here: http://www.azurespeed.com/Azure/PsPing
After installing that you would run "psping 40.121.22.148:8081"
From Azure support: Successful pspings from a source that can't access the matchmaking would tell us there's something happening above layer 4, and the Azure platform is ok.
Thanks again for your patience!
Brett