I could not sleep this night so I came up with some crazy ideas about how to show that FBI & USCIS dropped the ball on name checks.
I believe FBI does the same exact checks for other state agencies. Department of state comes to mind, when somebody applies for a student/professor visa or immigrant visa abroad. I doubt that any student or professor is waiting for a few years to get a visa so that he/she can start a new semester. For that very reason (professors could not back in time to teach students, etc.) Mr. Garrity was called to testify before the Congress.
So if we can get statistics from FBI showing that requests from Dep. of State are not pending for years, we will be able to dispute all that BS about "lack of resources", "processing requests in the order they've been received", "it can take years to resolve a name check".
I also believe Dep of State has much better computer system than USCIS (consulate cannot rely on shipping magnetic tapes to FBI from (no offence) the middle of nowhere).
I also know for sure the same check is run when somebody applies for a sensitive government position. There is a form called "FBI Name Check Waiwer" which has to be signed by somebody who is applying fo such a position. Do you think any of those applicants are waiting more than a month?
I'm back from vacation, so I'll try to catch up with the events here on the forum, too.
I personally don't know if FBI does the exact same type of name check for the foreign visa applicants. Remember, before Nov. 2002 FBI was already conducting a much simpler name check process, which included only the "main" file system search, similarly with the today's FOIPA requests. They added the "reference" file search only after Nov. 2002. Is it possible that for the visa applications they still do only the "main" file search? I don't think that you can find this out reliabily. This probably enters in the sensitive information category (with good reasons) and they will not let you know.
If you apply for a Department of Energy position which requires "Q" type security clearence, this may take more than a year till is done, so your second argument is also not necessary valid. But I don't know how that security clearence is compared to the immigration benefit related background checks.
My point is that there is no solid evidence to assume that "one size fits all" applies to all types of the background checks.