A number of states, as a result of a bunch of lawsuits, have passed "limited immunity" laws that protect employers from giving factually accurate references on former employees.
Unfortunately, many employers take the stance that (1) it won't stop a disgruntled former employee from *filing* a suit (costing big bucks just to get a dismissal) and (2) it's simply easier to verify dates of employment and nothing else.
I should think that most employers would keep rudimentary records on past employees semi-indefinitely so that they can verify employment, but I don't know for sure.
I was reading an article that mentioned several folks that have worked for a half-dozen dotcoms in the past 5 years, all of which are now gone, and with them, the prospective employer's ability to verify employment and get references -- unless the employee can track down a former boss at their current position mowing lawns or painting houses.