What I've been working on lately is a Workflow project that identifies machines which haven't used the software (VIsio, Project, etc) for over XX days, then when that condition is met sends an email to the Primary user of the machine notifying them that the software will be uninstalled. It then adds the computer to a collection for Uninstall, and the next configuration request (or immediately if you force a config update as part of the Workflow) the software is removed.
I am also planning on extending this to a sort of "uninstall portal" that the user can use to request software from our catalog to be removed. We may be in a bit of a different situation as we have monthly software-specific chargebacks for each application which we bill back to the user's cost center each month, so it is in the users' financial interest to not keep a copy of Visio they haven't used for 6 months (particularly when they can re-request it from our Software Portal easily enough).
If you don't have any bill-back method in place, I don't think there is much interest by the user to remove the software, since as far as they're concerned it isn't hurting them to have it "just in case". In my opinion, a Metering-driven approach is much more beneficial. We just went through our Pilot of this workflow and uninstalled over 300 copies of Visio (Std. and Pro.) and replaced it with Visio Viewer 2010 SP1; this saved over $11,000 in software licensing. That's a real value-added service you can provide, and a number you can give to Management to show another benefit of your investment in Altiris.
You mentioned manually executing your planned process...this is just wasted time and effort which could be better spent on other work. Automation is the name of the game (at least at my company), and anything that can be reliably automated should be as long as it makes sense.