Obviously I don't want to cycle through the entire collection
Não é óbvio para mim. Quão grande é essa coleção?
Enfim, por que você teria que percorrer toda a coleção? Coloque-os em uma lista ordenada pelo tempo de expiração. Desde que o tempo avança, você pode descartar tudo o que expirou. Então você só precisa verificar se o primeiro elemento é atual. Quando expirar, descarte-o e use o próximo.