I have had very different results >from the USCIS (Formerly the INS). I
have requested documents for many relatives and received in quite a
reasonable amount of time an initial response and then a packet with the
documents requested.

Perhaps it is the specific address used. I use:

National Records Center
Attn: FOIA Officer
PO BOX 648010
Lee's Summit, MO
64064-8010


R. Byer
Researching:
BYER/BAYER/BAER (Zeimiai, Lithuania -> Vilijampole, Lith -> NYC, USA
->Bangor, Maine)
COSTRELL/KOSTRELL/KASTREL (Kurenets, Belarus -> NYC, US -> Detroit, Mich)