Gmail rejects emails. Openspf.net fails the tests

Solution 1:

Microsoft has a nice wizzard. Maybe it can suggest some changes?

http://www.microsoft.com/mscorp/safety/content/technologies/senderid/wizard/

Solution 2:

After 50 days of trying and googling for a solution, Gmail started to accept our emails. They pass to inbox in normal way (they are not tagged as spam).

I didn't make any changes or any other tries during last 15 days. I don't know is it bureaucracy or some algorithms that take so long, but to my mind it took 10 time longer than it should. 5 day penalty for our weak security is enough.

By the way, unlocktheinbox.com now passes the test, openspf.org test is still reporting a failure. Looks like my situation is too complex for the test. I would fix my PTR and HELO names to match domain name.

However it took already a week after we asked our ISP to change PTR and it's still remains unchanged... One more bureaucracy issue.

Thanks for everyone's help.