Again gmail s2s: dialback not working ("invalid")

I followed the discussions of gmail s2s problems. It seems like google has fixed everything, but it's still not working for me. I guess my problem has another reason, as I recently moved to a different (virtual-) server. Before that it was working.

Other XMPP servers work fine, I just got problems with the gmail dialback (full log at http://pastebin.com/d0XsUFh7):

=INFO REPORT==== 2010-08-15 23:30:59 ===
D(<0.394.0>:ejabberd_s2s_out:268) : s2s_out: connecting to {74,125,47,125}:5269
=INFO REPORT==== 2010-08-15 23:30:59 ===
D(<0.395.0>:ejabberd_receiver:320) : Received XML on stream = ""
=INFO REPORT==== 2010-08-15 23:31:00 ===
D(<0.395.0>:ejabberd_receiver:320) : Received XML on stream = ""
=INFO REPORT==== 2010-08-15 23:31:00 ===
D(<0.394.0>:ejabberd_s2s_out:340) : recv result: {"gmail.com","hinrich.de",[],"invalid"}
=INFO REPORT==== 2010-08-15 23:31:00 ===
I(<0.394.0>:ejabberd_s2s_out:353) : Closing s2s connection: hinrich.de -> gmail.com (invalid dialback key)

This is what I checked:

1. Resolving seems to work, it get's googles IP... (as can be seen in the log)
This is my inetrc:
{lookup,["file","native"]}.
{host,{127,0,0,1}, ["localhost","hostalias"]}.
{file, resolv, "/etc/resolv.conf"}.

2. Firewall has no restrictions right now:
# iptables -L
Chain INPUT (policy ACCEPT)
target prot opt source destination

Chain FORWARD (policy ACCEPT)
target prot opt source destination

Chain OUTPUT (policy ACCEPT)
target prot opt source destination

3. SRV records seem right:
$ dig +short -t SRV _xmpp-server._tcp.hinrich.de
5 0 5269 178.63.197.6.

4. And Reverse-DNS also:
$ host 178.63.197.6
6.197.63.178.in-addr.arpa domain name pointer hinrich.de.

I don't have a clue anymore what could be the problem. I changed the DNS records already 2 weeks ago, so there should be no old cached entries.
I'm using ejabberd 2.1.5 and tried the binary installer as well as the distribution package of debian lenny.

Has anybody got an idea?