How would someone compile their past personal residence information
(address and phone number) for 20 years moving an average of about
once every year? (with minimal contact of friends/relatives)

This isn't a complete answer, but often your credit report will have a
few of your most recent mail forwarding addresses on it.