TL;DR; Azure Queues (and any other component of Azure Storage) have 20000ops/sec limit per storage account. Those guys used a single storage account for all queues. They increased load a bit, and hit this limit. Azure throttled them every now and then to a complete stop.

Solution was to have multiple queues in multiple storage accounts.

IMHO, important information to keep in mind when building horizontally scalable service. Every message channel/storage should be ready to be sharded in some way.