As of last week, we changed nothing and registrations just work again.

There was no notice from Microsoft or anything about an outage or any logs that would indicate what the error was.

The main takeaway from this is in my opinion: If you use Azure Notification Hubs they sometimes just don't work and there's nothing you can do about it.