There are many similar questions to this one but suggestions are usually pretty generic, like go check your server against that bulk blacklist checker.
So my mail server has a correct SPF record, a PTR and signs all messages with DKIM but still every message goes to spam in Gmail by default.
What can be done in this case?
GMail provides a message that tries to explain why the message end up in spam but it is quite vague: " It contains content that's typically used in spam messages" (http://goo.gl/z2ASq). Linked page has something that proves my suspicions: "Messages sent from accounts or IP addresses that have sent other spam messages". But again, have no clue how to get around this.
Here is an example header:
Received: from mail.somehwere.com ([XXX.XXX.XXX.XXX]) by mx.google.com with ESMTPS id y59si1359634wey.46.2012.10.02.07.28.54 (version=TLSv1/SSLv3 cipher=OTHER); Tue, 02 Oct 2012 07:28:54 -0700 (PDT) Received-SPF: pass (google.com: domain of firstname.lastname@example.org designates XXX.XXX.XXX.XXX as permitted sender) client-ip=XXX.XXX.XXX.XXX; Authentication-Results: mx.google.com; spf=pass (google.com: domain of email@example.com designates XXX.XXX.XXX.XXX as permitted sender) firstname.lastname@example.org; dkim=pass email@example.com DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=somehwere.com; s=default; h=Content-Transfer-Encoding:Content-Type:MIME-Version:To:From:Subjectate:Message-ID; bh=LFhHIhWWdKms4f3jo157plOkAJzpbSt1ILThu4epfsI=; b=N2raCWyGEvCEp6OJBIpvjWv/yCivYzqTm9go+hLKUH3T5Hi61VvL2cv3c52ivBEzNiOOlzLTWIdK4CfdjKSdStJ1ZD5itVse27P17DTh38b9cXNxXUoK89abTd4GxgO/; Received: from localhost.localdomain ([127.0.0.1]:54505 helo=somehwere.com) by mail.somehwere.com with esmtpa (Exim 4.80)