Yes, I got the subfolders part but you didn't mention that they were sharing the subfolders. It sounded like they were only changing the permissions on the subfolders rather than creating shares.
If that is the case then there isn't anything that you can do about it. Even if you take away the explorer tool bar, the shares are available through many other methods. You can launch IE and type \\server\share in the address bar. You can go to Start --> Run and type \\server\share on the run line. Also, any shares that users have already opened documents from during their surfing will still be available to them as a shortcut via My Network Places unless you change the security. Then there's the consideration that any virus that spreads through open shares will have a heyday on your network. This goes back to the whole security by obscurity thing.
I know that you're saying that education doesn't work, but they're asking you to treat a single symptom of the problem instead of fixing the problem. The system is functioning as intended, and trying to engineer a fix to the "problem" that attempts to circumvent the system's designed functionality will be extremely time consuming, frustrating, and in the end, unsuccessful.
The fix is to not create shares where everyone has full rights. Since this is something that you have to do intentionally, there's no reason why the users creating the shares (and lets face it, they probably shouldn't be doing that anyway) can't take responsibility for setting the security properly. If they create a share and explicitly allow 'Everyone' access to it, then they have nobody to blame but themselves when someone who they didn't want to have access to it gets to see it. If they can't take responsibility for it, then they shouldn't have that power to begin with.
My suggestion is to take away the "Full Control" permissions from the users. Limit them to read/write, clean up the shares that are there, and then you shouldn't have any more problems with users incorrectly creating shares.
