Use a VERP. Another robot should reply to the VERP, whereas a human should reply to the Reply-To.1) How do I distinguish the messages from these robots from spam? A lot of them advertise these horrible services.
Clueless bots are always going to be a problem (see vacation messages). You have to use cluefull bots and complain to the ISP of those who use dumb bots.2) How do two people who use the service talk to each other? Your message to me will be challenged by your service. There is a strong possibility that some of the more clueless bots will livelock here, others will never allow the communication.