What data structure or mix of data structures would I use for a concurrent queue that allows for bulk and specific deletes?

Here is my problem, I need a data structure that behaves like a queue, but has some other properties:

• I should be able to easily delete items given a tag (every item in this queue has a tag that groups them)
• I also need to be able to delete one item given a key (all items added to the collection will have such a unique key). Here, if it simplifies things, I could remove by tag and key if it would make it faster.
• This collection is used in a concurrent environment so using as little locking as possible would be awesome
• It should have the usual FIFO properties of a queue. I do not need to access items not in head, but i need the deleting behavior above to work.

I'm using C# to build this solution but I'd be much more interested in algorithms and data structures definitions as I hardly believe any of the available collections meet my needs.

Papers, books, blog posts and any other kind of reference to this are really welcome.