Mark Jaquith already admitted that by pointing out that his list was simple quoted shortcodes only. However, even more complex constructions could be noted in a section of the directory that lists plugins w/ indeterminate shortcode names, for example.

Ultimately, the problem could be solved if WordPress added an optional plugin header parameter:

Plugin Name: My Plugin
Plugin URI: http://example.com/
Shortcodes: [shortcode], [shortcode2]

It'd be easy to parse automatically, could be revealed in the WP UI in some way, and so forth.