Interesting idea. Probably the easiest thing to do here would be to either create a list of 'term' programs or 'non-term' programs along with a list of excluded programs. Of course, we would want to figure out which list, 'term' or 'non-term', was going to be shortest before deciding which to make.
To skirt the setup "Create Cygwin/XFree86 icons?" step, we could simply stuff the above lists and a modified version of your script in a new package called, for example, XFree86-start-menu-icons-4.3.0-1.tar.bz2.
I would go a step further. As Brian (and others) have pointed out, the default X install contains a bunch of programs that aren't really "important", e.g., xlogo. Creating a huge list of them in the start menu would indeed be "clutter", and I concede that what I initially suggested (shortcuts for all clients) would be silly. I don't know the functionality of 90% of what's in /usr/X11R6/bin/*.exe, but I'm sure some things are used more widely than others, and some are more and some less appropriate for the start menu.
Here's what would be useful, though: if I install a Cygwin-ized Emacs, for example, there should be a shortcut for it in the start menu. Granted, I should be taking this request to Emacs' packagers, but the folks here have unique expertise suited to this task, and perhaps could work with apps' packagers to provide this functionality.
It would be a bad idea to install icons for apps that aren't there, though, and so I'm tempted to argue against a XFree86-start-menu-icons-4.3.0-1.tar.bz2. On the other hand, there may be a smart way of writing the scripts for that tarball, such that a particular icon is installed only if the app is actually present. This way Emacs and all the other packages wouldn't have to be altered.
The rule of thumb for what's a good application to add to the start menu could be this: if you use it as a GUI, and you can get reasonable mileage out of the app without passing varying parameters on start up, it should have a shortcut. (Filename parameters would be easy exception to pass using the standard windows technique of drag-and-drop to start menu.)
-JT