A hint for email providers
Here is something that I shouldn't have to say to all sorts of email providers but apparently need to:
If someone says that you have spammed them, your first reaction should not be to proclaim that you are a legitimate business (and that you don't spam and that you have strong policies and so on); your first reaction should be to profusely apologize and attempt to open a dialog so that you can fix the situation.
There are a number of reasons for this, assuming that you are a legitimate business and actually want to deal with any spam problem that you have. First, any public comments are the tip of an iceberg of your problem; for every person who says something in public that you can find there are probably at least ten who have just quietly done something about your email. This means that you have a bigger problem than you can see and you need to do something about it fast, and so you actually need the information that this person might be able to provide if you approach them nicely.
The second reason is that it is good public relations. Regardless of what actually happened, you have done something that annoyed this person. If you go around proclaiming your innocence, you are coming very close to also calling them a liar, which rarely goes down well with the already irritated; you are unlikely to do anything except harden their unfavorable reaction to you. By contrast, apologizing and working to solve the situation both acknowledges their situation as real and is more likely to leave them feeling positively inclined towards you.
(Hint: it does not matter if you did not actually, technically, spam them. What matters is that you left someone with the belief that you did.)
The final reason is that it doesn't work. Regardless of the facts of your specific case, this particular well is already poisoned; too many spammers have spent too much time proclaiming their innocence for anyone to believe you. This includes bystanders, and remember that under almost all situations, the person you are trying to 'correct' can have the last word if they want to.
(This general advice is applicable in situations beyond spam, of course. For example, technical support.)