Yeah it's actually not that bad, because for example the BMV will likely upon request send you a duplicate driver's license to your address of record. Same for getting replacement credit cards. If you had utility services at that address in your name that's additional documentation. Also historical tax returns, bank accounts, etc.