An opt out button on a link request ... ha ha. That's a good one. If a person does not respond, then they are not interested in an exchange.
By its very nature a link request should be one and only one email to an address. There should never be a follow up email. There is nothing to "opt out" of. Sending in more mail to that address is spam.
Quite frankly, I would delete a link request with an opt out button or mention of CAN SPAM. An opt out button on unsolicited email is spam incarnate.
Back to the question of when is a link request spam. If you are responding to an email address put on a web site to solicit information about the web site; then it is not spam. It may be annnoying ... it is not spam. If you are sending a mass mailing to an email address you purchased, then it is spam.
I get hundreds of link exchange requests to info. It's all spam. I don't use the info address.
If you send a link request to a web site that does not have a link page. Then you being a stupid annoying person. Although I would not consider the email to be spam, I would consider you a spammy person.
My answer to the question is: Sending an link exchange request to a contact address on a web page that has a links page, and does not have something saying "No Link Exchange Requests" is not spam. There should at most one contact to the web site. Anything beyond that is spam.