Maybe what we need is a system where instant messages are allowed, but it imposes a cost of some kind to the person initiating it, so that it won't be used frivolously. Like the proof-of-work antispam captchas, except it should take ~30 seconds and be just once per conversation (defined as ending when 5 minutes go by without message; first replies are free).
We could also add a social cost by displaying how often each user has used this feature in the past 24 hours, next to their username.