RESTORE VERIFYONLY locks file in Azure Blob Storage
This seems very similar to:


FIX: Cannot remove backup file after you restore the database from Windows Azure in SQL Server 2014 or SQL Server 2012


From that Microsoft Support article:


  Symptoms  
  
  Assume that you use the RESTORE HEADERONLY or RESTORE FILELISTONLY command to restore a database from Windows Azure Blob storage service in Microsoft SQL Server 2014 or SQL Server 2012. After the command is completed, you cannot remove the backup file.
  
  Cause  
  
  The issue occurs because there is an infinite lease on the backup file. Some race conditions between internal threads cause the lease to be not released in some cases.


This is marked as first fixed in Cumulative Update 4 for SQL Server 2012 SP2. While the fix does not mention RESTORE VERIFYONLY explicitly, you should definitely check this out before reporting it as a bug.

The latest Service Pack for SQL Server 2012 at the time of writing is SP3, which will also include the fix mentioned above.

Finally, just to document something GregGalloway originally left in a comment on the question, you can remove active leases using a script in the following MSDN article:

Deleting Backup Blob Files with Active Leases