Не проще сделать отдельный тред, который будет обновлять словарь раз в t минут/секунд?
Тогда можно считать, что данные в словаре всегда актуальны и либо возвращать найденное, либо выдавать 500.
Из минусов — потенциально большее количество запросов к стороннему сервису.
Из плюсов — элементарная реализация, не требующая никакой синхронизации доступа к словарю.
Типа такого:

public class AutoUpdateCache<TKey, TValue> : IDisposable
{
    private readonly Func<IDictionary<TKey, TValue>> m_DataLoader;
    private readonly Task m_SyncTask;
    private readonly ManualResetEvent m_DisposingEvent;
    private volatile IDictionary<TKey, TValue> m_Inner;
    private readonly TimeSpan m_SyncPeriod;

    public AutoUpdateCache(Func<IDictionary<TKey, TValue>> dataLoader, TimeSpan? syncPeriod = null)
    {
        m_DataLoader = dataLoader ?? throw new ArgumentNullException(nameof(dataLoader));
        m_SyncPeriod = syncPeriod ?? TimeSpan.FromSeconds(5);
        m_Inner = new Dictionary<TKey, TValue>();
        m_DisposingEvent = new ManualResetEvent(false);
        m_SyncTask = Task.Factory.StartNew(syncRoutine, TaskCreationOptions.LongRunning);
    }

    public TValue GetItem(TKey key)
    {
        return m_Inner.TryGetValue(key, out var value) ? value : default(TValue);
    }

    public void Dispose()
    {
        if (m_DisposingEvent.WaitOne(1)) throw new ObjectDisposedException(nameof(AutoUpdateCache<TKey, TValue>));
        m_DisposingEvent.Set();
        m_SyncTask.Wait();
        m_SyncTask.Dispose();
        m_DisposingEvent.Dispose();
    }

    private void syncRoutine()
    {
        do 
        {
            m_Inner = m_DataLoader();
        }
        while (!m_DisposingEvent.WaitOne(m_SyncPeriod))
    }
}

Не проще сделать отдельный тред, который будет обновлять словарь раз в t минут/секунд?
Тогда можно считать, что данные в словаре всегда актуальны и либо возвращать найденное, либо выдавать 500.
Из минусов — потенциально большее количество запросов к стороннему сервису.
Из плюсов — элементарная реализация, не требующая никакой синхронизации доступа к словарю.
Типа такого:

public class AutoUpdateCache<TKey, TValue> : IDisposable
{
    private readonly Func<IDictionary<TKey, TValue>> m_DataLoader;
    private readonly Task m_SyncTask;
    private readonly ManualResetEvent m_DisposingEvent;
    private volatile IDictionary<TKey, TValue> m_Inner;
    private readonly TimeSpan m_SyncPeriod;

    public AutoUpdateCache(Func<IDictionary<TKey, TValue>> dataLoader, TimeSpan? syncPeriod = null)
    {
        m_DataLoader = dataLoader ?? throw new ArgumentNullException(nameof(dataLoader));
        m_SyncPeriod = syncPeriod ?? TimeSpan.FromSeconds(5);
        m_Inner = new Dictionary<TKey, TValue>();
        m_DisposingEvent = new ManualResetEvent(false);
        m_SyncTask = Task.Factory.StartNew(syncRoutine, TaskCreationOptions.LongRunning);
    }

    public TValue GetItem(TKey key)
    {
        return m_Inner.TryGetValue(key, out var value) ? value : default(TValue);
    }

    public void Dispose()
    {
        if (m_DisposingEvent.WaitOne(1)) throw new ObjectDisposedException(nameof(AutoUpdateCache<TKey, TValue>));
        m_DisposingEvent.Set();
        m_SyncTask.Wait();
        m_SyncTask.Dispose();
        m_DisposingEvent.Dispose();
    }

    private void syncRoutine()
    {
        do 
        {
            m_Inner = m_DataLoader(); // Atomic volatile write of the reference variable
        }
        while (!m_DisposingEvent.WaitOne(m_SyncPeriod))
    }
}