1) In SOME cases programs will leave a Registry Entry with some bare data that tells the system it has been installed before, such as keeping user saved setting stored in local temp. However, often, most programs when uninstalled remove all temp data, and registry values unless an option to save personal settings.
2) You can, for most software, copy most installed programs, including their temp files and user setting files, and then use RegEdit to export the registry of the software. Than on the new machine you can import the stuff back to its respective locations, and import the registry value. In most sane scenarios this works fine. Some programs though log the systems ID, and other identifiers to prevent this.
Note recovering data from a formatted hard drive is often fragmented at best, as the drive will write in blocks and the new OS and data will likely overwrite a lot of data. Some recovery is possible, but usually in a third party environment.