For 4473 address: you typically only need some proof of government-recognized address. Lots of stores will accept a fishing or hunting license, which can themselves be acquired without proof of address.
The "clerical mistakes" around NICS are an absolute nightmare from what i hear... the government digs their heels in hard once you're in the database. The law does allow you to recover your legal costs, but ONLY if you get a judgement in your favor. Usually they drop the case immediately before judgements, and you're on the hook for your $10k+ costs.