Slow Collections

I have a collection in my project (its very large!), that acts as a queue
during runtime.
I add a few thousand objects to it, and later on remove them. This happens
many many times (hundreds of thousands) over a long time. I can test how
many (and for how long) loops my program has been through and after 12 hours
of running the same loop the time the loop runs for its getting longer and
longer.

I completly emptied the collection of data each time the loop starts and it
still gets slower and slower over time. If I then after hours of running
this, I set my collection to a New collection, it starts running at full
speed again. Ive tested things all over the system and know it to be the
collection slowing it down. It takes a good few hours for it to slow down
(any many many jobs) but as my software is created to run whole
infrastructures and can not slow down. It runs 4000 jobs the first hour,
then by the time you get to 12 hours later, its down to 1000 jobs and hour,
restting the collection to a new one, makes it go back up to 4000. If needs
be I will have to once an hour create a new collection and shift things
over, but I thought I would check in here first to see if any1 has seen or
heard anything like this.

Also to note, the memory is fine. Bout 200 meg constant, its designed to
grow to an adiquate size and then stay there, so thats not an issue.