It comes across as extortion. "Pay us money or we'll put up a sign saying you're a bad person for...doing exactly what the Inernet designed for." Surely this will kill their SEO as well.
I suspect one could try a defamation case against this. I believe it has been tested in court that linking to a website is freely allowed, and doing so does not therefore constitute misuse of the target site. It would therefore seem to me that claiming that a business you have no existing business relationship with is breaching your terms and conditions for doing something within their legal right, is pretty dodgy behaviour.