I found this great posting from "pralay" on background checks:
1. IBIS (done by USCIS themselves) - this check has validity of 90 days -
this check is against IBIS (maintained by USCPC - Customs and Border Patrol)
using applicant's full name and date of birth (without place or country of
birth). This check is done by USCIS staff on the computer terminals
connected to IBIS. A no hit is termed "IBIS OK" in BCIS' jargon. An "IBIS
DNR" (Does Not Relate) is when a match exists but does not relate to the
applicant, which is, in other worlds, a no hit as well. IBIS is exempt from
FOIPA requests, that is, a person cannot use FOIPA to find out if his/her
name is in IBIS.
2. FBI Fingerprint (FD258) Ident against NCIC database - this has a vaildity
of 18 months, per a MOU between FBI and USCIS. Any applicant can call FBI
NCIC (Clarksburg, WV) at 304-625-3878 to find out if his/her fingerprint
ident. result has been sent back to USCIS. Work through various voice prompt
at this phone number to talk to a live representative. The results of this
check are normally returned within 24 hours for person with no criminal
records or outstanding warrants. No hit is termed "NO IDENT" in FBI's
jargon. An FOIPA request (with FD258/fingerprints) would reveal if an ident.
record exist or not.
3. FBI Name Check against Central Records System (CRS) - this check
basically meant to find out if the applicant has ever been subject/target of
any FBI investigation. There is no documented validity period for this
check. This check can take anywhere from 1 day to 1 year. No hit is termed
"NO RECORD" in FBI's jargon.An FOIPA request would reveal if a record exists
or not. FBI may not disclose full details but at least tell you if a record
exist. Also, presence of a record does not mean that it is something
negative.
4. CIA. According to my attorney, this check is conducted on individuals from certain nationalities only. Validity unknown.