This was what i first checked too. At some day i started to receive more and more Mail Delivery Failure messages in my Inbox from addresses that seemed to be ra

This was what i first checked too. At some day i started to receive more and more Mail Delivery Failure messages in my Inbox from addresses that seemed to be random or of some Chinese names. I just saw them because a catch all address was configured. Some MTA showed the messages and it was obviously some Chinese spam. After configuring SPF records this stopped immediately. So this might can be the reason why google thinks you are sending spam. Even if not, you will better your rating with them configured.