you can go to ussearch.com for people search, you need enter your wife name and see which one matchs her. You need pay some money to pull out her background. See any record for her in that time, usually they list all information, address, neighbours...., but definitely not sure they can have information back to 2000. You can try if no other choice.
or how about your tax return, credit report,