You can also use psexec to run VBS scripts, or VBS scripts with user escalation (your users are running as users and not local admins, right?:P) compiled into an exe via Visual Studio Express.
Alternatively OP could ask for an agent based system such as Kaseya, Altiris, etc.
I really don't understand why a company would ban GPOs, however. That just reeks of incompetent management.
Some of the micropayments concepts are particularly interesting, because we're literally talking about nickels and dimes.
"Add $50 funds for 5000 News!" "Read this article for 2 News!"
I actually suspect that it would work quite well, but it's very foreign.