[SalesForce] custom button visibility list view

I'm afraid you have to create a VF page and use it as a custom VF tab (since you can't even override the Contacts Tab).

Sir, it's an awesome question cracks me up that we can't do such a simple thing :) Does it really have to be a related object that drives the logic? Won't a (multiselect) picklist on Contact do, as nasty as it sounds in terms of maintenance?

EDIT: 3 more ideas:

1. You can build listview filter on contacts using a Campaign (I won't be surprised if it works for only when you have "Marketing User" ticked) - would that work?
2. Would it work for you to enable tags (maybe only personal tags)? They're still fairly easy to search from sidebar/global search and look like working with them is less hassle than inserting new entries on a related list. Maybe even combine it with a list view button for mass add/remove tags...
3. Similar one about following them with Chatter?