When you obtain a copy of your credit report from each of the major credit bureaus, there will be information about the process to dispute any information on the report that isn't accurate. Follow the instructions to the letter - this is not the place to try to make the process bend to what is convenient for you. You can file a dispute online or in the mail,but any dispute must be in writing. Hope this perspective helps!
Dispute the report with the credit bureaus. If they don't fix it find a local consumer protection attorney and sue the collector for violations of the Fair Credit Reporting Act.
The information provided here is intended to help you be an informed legal consumer and is not a substitute for representation by an attorney.
You wrote, “PROVE that I was living at my correct address in 2009 with a bill, or with mail (I can't provide either: who keeps mail for over 4 years?“
A: Then my be a lot easier than you think: asked one of the utility companies to provide you with a list of payments going back to 2009; with computerization this might be a fairly easy task. also, if you own the house real estate tax bills, and of course there is the (Social-Security-#-redacted copy of your income tax return, or employer-provided record showing the address of payment on your W-2's in 2009.