Plesk 11.x / Windows :: DKIM-Signature Header Exists But Is Not Valid ERROR

I am having complains from our clients that their mails are always going to spam folders istead of inbox. I decided to have some tests and find out problems which couse the issue and solve them. We have PTR records correctly, Our IPs and domain names are not listed in any blacklists, And I checked "Use DomainKeys" checkbox for all our domains in mail settings.

These were all good and thought that all works well untill I ran a test on [URL].....

I opened a mail file (.MAI) and copied all content (with headers, contents and all) to that site and got a result like;

pts rule name description
---- ---------------------- ---------------------------------------------------
0.0 RCVD_IN_DNSWL_NONE RBL: Sender listed at http://www.dnswl.org/, no trust
[95.108.252.17 listed in list.dnswl.org]
0.0 URIBL_BLOCKED ADMINISTRATOR NOTICE: The query to URIBL was blocked.

[Code] ....

The 3rd line from the last confused me. "Message has a DKIM or DK signature, not necessarily valid" and "DKIM-Signature header exists but is not valid" parts of that report put a question in mind. Does the "Use DomainKeys" checkbox in the Plesk Panel really working? I mean, it creates all the DNS entries and all, but the email message is starting with a line "DomainKey-Status: no signature" and that supports the 2nd line from the last in that report.

The question is, what should I do to make DomainKeys work as it should? I am using the latest 11.5.30 Update #23 of Plesk Panel for Windows on a Windows 2012 Standart server with MainEnable Enterprise Premium. Enterprise version of MainEnable also has DKIM settings available for all the domains in its own panel, but it's disabled because I didn't set anything in there.