I was not aware of applying for the NARA documents first and I have requested my USCIS search in Feb. 2012- still do not have a response. The website has had the following disclaimer since April;
Index Search (G-1041) Requests are now being worked as received. Replies are generally mailed within 3 to 4 weeks.
Record Requests (G-1041A) received in January 2012.
Older Record Requests not yet closed are awaiting files or privacy screening. If you submitted a Record Request (G-1041A) prior to January 1, 2012 and have not received a file/response, you may contact us at the email address below.