You do not need an FBI letter in all states - depending on where your residency is, you only need a state police record from that state. At the embassy in Washington, DC and also at the consulate in NYC, I think, you do not need the FBI letter. Different consulate offices need different paperwork. You can private message me for more details. Another good thing is that if you are able to go to a consulate that does not require the FBI paperwork, you can greatly expedite the process (for example in DC I got my work visa the same day after some prodding by my company's lawyers, etc.)