Nodequeue has an option to create a tab on Node pages that links to: node/%/nodequeue. Entityqueue could add a similar page. This page would allow you to see all the queues that the entity can be added to. For any queues that the entity is already in, it would show a "Remove from queue" link, otherwise it would show a "Add to queue" link.
The only thing I can see wrong with the Nodequeue's implementation, is if the same node is in the queue multiple times (assuming this bugwas fixed), then clicking "Remove from queue" only removes the first instance of the node in the queue. We may want to consider a "Remove all from queue" and maybe a "Remove from queue position X" to give the user more control over which one is removed from this page.