If a company doesn't publish the protocol in use within, let's say 3 months of a valid request by a third-party then they'd be liable to a fine, perhaps something like $1 per day per registered user, plus costs of government and registered third parties in pursuing the interoperability request.

Small companies might escape, but if Facebook tried it they can't really run away. You'd need to be able to issue notices to ISPs to block those convicted of breaking the law, such orders are already part of UK law (against torrent discovery websites for example). Again you'd get some leakage but big providers like Microsoft couldn't feasibly expect enough customers to move to VPNs to bypass such a block.

IM client definition could be hard but in practice you'd have clauses requiring a judge to decide if the traffic exchange amounted to an IM communication. I see no problem with having a broad definition, if the definition were narrow then it would just get worked around. The definition would probably include email as a subset.

Were there other person-to-person communications protocols you are concerned would fall in the scope that definitely shouldn't be open?