Word [SPAM] added to subject of emails


New Email
Hello again,

We have a client which complains that email messages sent from our server (we are an esp) gets delivered to them with modified subject in which word [spam] is added as prefix.

What could be a problem? We have checked our ip records on all major blacklists and everything seems to be fine. Also, our SPF/Sender ID/DKIM records are good.

Could be a problem on their side eg. antivirus (they have avast)? Or somewhere in middle, eg. their hosting company?
All email accounts '@theirdomain.com' have the same problem.