Well, enumerating the Hashtable should be fast enough. There is
certainly some overhead in boxing and unboxing the DictionaryEntry
structure, but I'd expect that that's less than enumerating Keys and
reading each Hashtable[Key]. (Of course, my expectation may be wrong;
you should run some tests.)

I don't know what the performamce characteristics of a DataTable are
like; thankfully, I've managed to not yet need to touch a db from
.NET. But I find it hard to imagine that a table-based structure could
be faster than a simple, purpose-built data structure like a Hashtable
or ArrayList.

Could an ArrayList be faster? I'm sure it would be faster to walk the
list, looking for expired entries, but shifting 1000 (or 20,000)
key/value references to the left is going to be expensive - lots of
memory access at bus speed, and it'll purge the cache, too. Similarly,
finding your string Key is going to be a lot cheaper in a Hashtable
than in an ArrayList.