After the mgmt / company culture issues were solved, we dove into, as you mention app testing. What we did was the following:
1) IT Desktop was responsible for testing software that was part of sandard image: the OS, Office, general IE interactions, etc
2) Application support from various groups was responsible for testing their apps.
3) An SMS scan was done to identify all other non standard software installed on users machines. Users on this list were contacted to provide a business justification for having this software on their machine. If it did have a business need, these users were then shceduled to come in and test the software themselves. One thing to note is that we took a bit of a soft stance here; if a particular piece of non-standard software was not business critical, we did NOT uninstall it during lockdown deployment. We just wouldn't schedule it to be tested and if it worked, fine, if it didn't, too bad. This solftened the blow for some end users somewhat in that it lessened the feeling of the mean IT department uninstalling my app. A small thing, but reaps big rewards from a cutomer satisfaction point of view. And for us, eventually, as we roll out new hardware later this year or the next, we'll eventually catch up with these non business related apps and simply not re-install them.
Your testing will most likely find exceptions. I highly recommend, when doing testing, run RegMon and FileMon from the briliant Mark Russinovich at www.sysinternals.com
(now owned by Microsoft). If an app does have problems running without local admin, these tools might be able to pin point where the problems are. If you can isolate it, you can redo the permissions on that particular file or registry key that is having access problems.
No doubt you will also run into situations where you will just have to grant local admin privs to someone because of their job function (software developers, etc) or because there was no other way to get the particular piece of software running without local admin. In these cases, users have to fill out a form, giving a valid business reason for the access and this is reviewed and approved by the security operations group. The user then gets a special account we call a sys account that is put into the local admin group. i.e. If my normal username was cadillacgolfer, we would create a user account called syscadillacgolfer which I would need to log in as to perform any admin functions. Whether or not this account needs the same kind of access across the domain as my regular account will vary depending on the situation, but we've found that this is the excpetion and not the rule.
What is also critical is having a solid process in place for dealing with testing apps, excpetions, managing software licensing (aside from security concerns, this is one of the great benefits of this project) etc after your roll out happens, and this obviously has to be in place before you do the roll out, otherwise you will run into a whole bunch of user issues.
Having IT mgmt back you during this whole thing is critical, especially for those users that will complain mightly about their daughters install of Barbie's Dream House doesn't work without local admin. Wait a minute, why do you have Barbie's Dreamhouse loaded on a company laptop to begin with?