When you start talking about “a very large number of records, processes, etc.,” I freely admit that I find myself asking, “well, why not use a database table for this?”

Sure, there’s going to be a little bit of overhead, but in the grand scheme of things you probably don’t care.   A database table could hold any number of rows, and it could, through appropriate columns, also support any number of “queues.”   You could indicate that the record had been processed by, say, posting a non-NULL value into the row, and... that would also be a great place to put any other information (status, anyone?) that you might see fit to place there.   You also know that the values will be persistent.   If you wanted to do statistics and so-forth, having a persistent record of the event just might be the bee’s knees.

In other words, my instincts tell me that using a database table in this instance (a) won’t be “egregiously painful,” and (b) just might be useful.   “It’s not contra- indicated, and it just might be ... indicated.”