The new API has the .Exists() function call. Just make sure that you use the GetBlockBlobReference, which doesn’t perform the call to the server. It makes the function as easy as:
public static bool BlobExistsOnCloud(CloudBlobClient client,
string containerName, string key)
{
return client.GetContainerReference(containerName)
.GetBlockBlobReference(key)
.Exists();
}