<p>I want a data structure that will allow querying <em>how many items in last <strong>X</strong> minutes</em>. An item may just be a simple identifier or a more complex data structure, preferably the timestamp of the item will be in the item, rather than stored outside (as a hash or similar, wouldn't want to have problems with multiple items having same timestamp).</p>

<p>So far it seems that with LINQ I could easily filter items with timestamp greater than a given time and aggregate a count. Though I'm hesitant to try to work .NET 3.5 specific stuff into my production environment yet. Are there any other suggestions for a similar data structure?</p>

<p>The other part that I'm interested in is <em>aging</em> old data out, If I'm only going to be asking for counts of items less than 6 hours ago I would like anything older than that to be removed from my data structure because this may be a long-running program.</p>

I think that an important consideration will be the frequency of querying vs. adding/removing.  If you will do frequent querying (especially if you'll have a large collection) a B-tree may be the way to go:
http://en.wikipedia.org/wiki/B-tree
You could have some thread go through and clean up this tree periodically or make it part of the search (again, depending on the usage).  Basically, you'll do a tree search to find the spot "x minutes ago", then count the number of children on the nodes with newer times.  If you keep the number of children under the nodes up to date, this sum can be done quickly.