Hay varios enfoques para implementar el almacenamiento en caché, httpcontext es el más fácil, pero no es necesariamente el peor. Eche un vistazo a memcached o MS Velocity, que se pueden utilizar como backends para ASP.NET Cache. Especialmente Memcached tiene una reputación de hacer un muy buen trabajo.
En cuanto a la política de caché: debe decidir qué funciona mejor para usted. Personalmente eliminaría la lista completa del caché al actualizar/eliminar en lugar de tratar de averiguar si la entidad está en la lista, ya que se necesita una cantidad de tiempo no trivial y debe tener en cuenta los problemas de concurrencia (bloqueando la lista, ya que alguien podría hacer una actualización/eliminación de otra entidad). A veces tiene sentido actualizar una entidad en su lugar (si tiene un objeto completo con todos los datos que necesita), a veces es una pérdida de tiempo, porque debido a algún cambio de estado la entidad debe moverse a otro lugar (por ejemplo, cuando ordena por LastChangedDate, etc.)
No olvide optimizar su código de base de datos también para que no le tome demasiado tiempo actualizar la lista de descarga.