Sorry to tag a post onto yours but Im having the same exact issue, Im also trying to do this with an ASUS G73JH with Win7 64.
Here is my process, Im sure its exactly like yours:
1. Download AMD Mobility Radeon DriverVerification Tool Version 13.9
2. Run and Install
3. After AMD Catalyst Mobility program is running I hit start download, after it downloads I hit install and nothing happens.
4. I run the file I just downloaded from the folder and am told that it is incompatible with the versionof windows that Im running.
5. Try to do same thing except as running as administrator and am told that windows cannot find the file, make sure I have typed the name correctly
I never fully uninstalled my drivers like the OP, but I still need to update them in order to get a few programs to work again.