Were they set up initially, or after you noticed problems? I wonder if prior messages routed to the spam folder that people haven't marked as non-spam count against you for a certain prior period.
I added them after I noticed problems really. Postfix and Dovecot have somewhat of a learning curve (I started up and trashed a few VM's before I got it right). I ended up using IRedMail, the defaults are pretty much Gmail ready.
I don't know about prior messages counting against you, given what I've seen it seems to makes sense. Without insider info we can only speculate.