There is no way to bind it to a specific theme unless you contact theme authors and they link back to you at some point (on theme activation with yellow message on the top or in their admin menu etc). As you suggested yourself, a plugin is supposed to work with any theme.
Theme and plugin markets could handle this by indicating that their plugins work with their themes only but this is a corporate restriction and cannot be applied technically.
What could be do is when you release something, you could name and describe it so it’s pretty much obvious (such as here – http://wordpress.org/extend/plugins/headway-views/ ). Also, in your plugin you could check for the currently activated theme (see get_current_theme ) and output some error message from within your plugin that it’s inappropriate choice.