Depends a bit on the OS, also.
With XP/2000/NT indeed desktop lockdown helps a lot. Just make it impossible to install their own software on laptop. As to Internet downloads and e-mails, maybe you can try blocking through the ISP's proxy. (If they have been made it technically impossible to use another ISP...).
This still leaves open the problem that EXE's can be _run_ from diskette, detached from e-mail etc. etc. For this, we use quite tricky mechanisms; extra shells on NT and multiple virtual machines under W2000 Pro. So I don't know whether this risk is worth the effort in your case; our case is the 5th generation of laptops in a financial institution which of course has heavy reqs.
Hope this helps,
- The Netherlands