@GertArnold were absolutely right, thanks buddy!

The problem was that .Contains() is too slow receiving a large numbers of items and was causing this strange behavior. To fix it I followed the answer pointed by @GertArnold that lead me to another post.

The strategy is break the large amount of items in chunks and create multiple queries in the end, it may sound weird that many queries will run faster than a single one, but I've made some benchmarks before adopt the solution and the code proven to be around 30% faster even running 14 queries (in my case) instead of a single one.

Here is the final code:

public async Task<List<StoreProductCatalogPrice>> GetCurrentByProductCatalogId(List<Guid> productCatalogsIds)
{
    var chunks = productCatalogsIds.ToChunks(500);
    return chunks.Select(chunk => DbSet.Where(c => chunk.Contains(c.StoreProductCatalogId))).SelectMany(x => x).ToList();
}

This extension method breaks a single IEnumerable<T> in smaller ones according the quantity you pass by parameter. This method was posted also by @GertArnold (thanks again) and can be found here

public static IEnumerable<IEnumerable<T>> ToChunks<T>(this IEnumerable<T> enumerable, int chunkSize)
{
    int itemsReturned = 0;
    var list = enumerable.ToList(); // Prevent multiple execution of IEnumerable.
    int count = list.Count;
    while (itemsReturned < count)
    {
        int currentChunkSize = Math.Min(chunkSize, count - itemsReturned);
        yield return list.GetRange(itemsReturned, currentChunkSize);
        itemsReturned += currentChunkSize;
    }
}