Azure BlobBatchClient.DeleteBlobsAsync always return 404 blob not found

I am experiencing a very strange behaviour when trying to do a batch delete blobs in a container. Having the following code (note some of the code is omitted or edited for brevity and security reasons):

var blobServiceClient = GetAzureBlobServiceClient();
var container = await BuildAzureContainer(blobServiceClient);

var blobsToBeDeleted = new List<Uri>();

var thumbImage = removedMedia.Path.GetThumbImageName();
blobsToBeDeleted.Add(new Uri("https://account-name.blob.core.windows.net/container-name/blob-name"));

if (!string.IsNullOrEmpty(thumbImage))
{
    blobsToBeDeleted.Add(new Uri("https://account-name.blob.core.windows.net/container-name/thumbs/blob-name"));
}

if (blobsToBeDeleted.Any())
{
    var batch = blobServiceClient.GetBlobBatchClient();
    await batch.DeleteBlobsAsync(blobsToBeDeleted, DeleteSnapshotsOption.IncludeSnapshots);
}

Using Azure.Storage.Blobs(12.9.0) and Azure.Storage.Blobs.Batch(12.6.0) Right before I try to do the batch delete I am uploading the images to Azure and confirming they are uploaded and exist in the container. The response from Azure is:

System.AggregateException: 2 batch operation(s) failed. (The specified blob does not 
exist.
RequestId: **removed**
Time:2021-06-18T08:16:15.2409894Z
Status: 404 (The specified blob does not exist.)
ErrorCode: BlobNotFound

Tried also to get the Uri using:

container.GetBlobClient("blob-name").Uri

or

container.GetBlobClient("thumbs/blob-name}").Uri

which also returns a correct url but with no luck.

I have checked and the URLs I am adding to the list are exactly the same with the active ones in Azure. No matter what I am doing the response is the same - all batch operations return BlobNotFound. For instance if do the following with the same blob:

BlobClient blob = container.GetBlobClient("container-name/blob-name");
await blob.DeleteAsync(DeleteSnapshotsOption.IncludeSnapshots);

The blob is successfully deleted. I am really struggling with this and cannot find what is causing this behaviour especially when I am able to delete the same blob but not in a batch. Am I missing something or there's something happening with the SDK? Decided to write here before opening a new issue in GitHub.

Any help would be really appreciated.

P.S. I am sure this was working a couple of months ago and the only thing changed is NuGet package updates.