Appearing in the spam email

We have been contacted by some online magazine with the barter offer: appearing in each others next email campaign(newsletter).

Now I have subscribed to their newsletter and the first one I received hit my Spam folder on Gmail. Checked on Yahoo and the same - Spam folder.

When asked their representative he said that "we know it, but there is nothing we can do..."

The question is how can it impact our company if our ad/company name/other info will appear in the spammed email body?

I think you have to look at this another way. If you received the newsletter as a customer of that company, would you value it? Is it in fact spam? Associating yourself with a company that spams people may have a reputational impact. Have you seen the companies policy on campaigns, what is their send criteria, how often do they send? Are they complying with data protection legislation?

At a technical level, you can't be blacklisted as it's their email domain, it's their IP address. They do target certain content patterns or certain words of which these are evolving but can't see this being an issue.

You could easily look up their email servers to check if they are blacklisted. If the content looks professional given its been filtered out by two different systems then it does suggest they are blacklisted (or the service they use is blacklisted).