There are a couple of things you can do:
(1) if you have a limited amount of allowed applications, you can
use AppSec from the Resource Kit to allow only those. See:
320181 - HOW TO: Use the Application Security Tool to Restrict
Access to Programs in Windows 2000 Terminal Services
http://support.microsoft.com/?kbid=320181
257980 - Appsec Tool in the Windows 2000 Resource Kit Is Missing
Critical Files
http://support.microsoft.com/?kbid=257980
(2) you can use Group Policies to restrict access to all kinds of
things. I understand that you have tried this, but something
didn't work. You can use gpresult from the ResKit to check which
GPOs are affecting the users.
278295 - How to Lock Down a Windows 2000 Terminal Services Session
http://support.microsoft.com/?kbid=278295
260370 - How to Apply Group Policy Objects to Terminal Services
Servers
http://support.microsoft.com/?kbid=260370
(3) you can use NTFS permissions on the file system to give users
only Read + Execute permissions on directories like C:\Program
Files
(4) you can give users only Read permissions on specific keys in
the registry. I find that the most important one is the
HKLM/Software/Micrsoft/Windows/CurrentVersion/Run
With only Read permission, users won't be able to install spyware
like Gator.
See also:
Securing Windows 2000 Terminal Services
http://www.microsoft.com/technet/treeview/default.asp?
url=/technet/prodtechnol/win2kts/maintain/optimize/secw2kts.asp