s2s connections start too long

s2s connections from my ejabberd server take 52 seconds to establish, which renders the server unusable.
The server has 2 IP addresses, but I patched it (http://www.ejabberd.im/node/511) to use only one address.
Here's my /etc/ejabberd/ejabberd.cfg (some comments removed):

% Local users:
{acl, local, {user_regexp, ""}}.

% Only admins can use configuration interface:
{access, configure, [{allow, admin}]}.

% Every username can be registered via in-band registration:
% You could replace {allow, all} with {deny, all} to prevent user from using
% in-band registration
{access, register, [{allow, all}]}.

% After successful registration user will get message with following subject
% and body:
{welcome_message,
{"Welcome!",
"Welcome to Jabber Service. "
"For information about Jabber visit http://jabber.org"}}.

% Only admins can send announcement messages:
{access, announce, [{allow, admin}]}.

% Only non-blocked users can use c2s connections:
{access, c2s, [{deny, blocked},
{allow, all}]}.

% Set shaper with name "normal" to limit traffic speed to 1000B/s
{shaper, normal, {maxrate, 1000}}.

% Set shaper with name "fast" to limit traffic speed to 50000B/s
{shaper, fast, {maxrate, 50000}}.

% For all users except admins used "normal" shaper
{access, c2s_shaper, [{none, admin},
{normal, all}]}.

% For all S2S connections used "fast" shaper
{access, s2s_shaper, [{fast, all}]}.

% Admins of this server are also admins of MUC service:
{access, muc_admin, [{allow, admin}]}.

% All users are allowed to use MUC service:
{access, muc, [{allow, all}]}.

% This rule allows access only for local users:
{access, local, [{allow, local}]}.

% Authentication method. If you want to use internal user base, then use
% this line:
{auth_method, internal}.

% Host name:
{hosts, ["neonus.sk"]}.

% Default language for server messages
{language, "en"}.

% Listened ports:
{listen,
[{5222, ejabberd_c2s, [{access, c2s}, {shaper, c2s_shaper},
{max_stanza_size, 65536},
starttls, {certfile, "/etc/ejabberd/ejabberd.pem"}]},
{5223, ejabberd_c2s, [{access, c2s},
{max_stanza_size, 65536},
tls, {certfile, "/etc/ejabberd/ejabberd.pem"}]},
% Use these two lines instead if TLS support is not compiled
%{5222, ejabberd_c2s, [{access, c2s}, {shaper, c2s_shaper}]},
%{5223, ejabberd_c2s, [{access, c2s}, ssl, {certfile, "./ssl.pem"}]},
{5269, ejabberd_s2s_in, [{shaper, s2s_shaper},
{max_stanza_size, 131072}
]},
{5280, ejabberd_http, [http_poll, web_admin]},
{8888, ejabberd_service, [{access, all},
{hosts, ["icq.localhost", "sms.localhost"],
[{password, "secret"}]}]}
]}.

% Use STARTTLS+Dialback for S2S connections
{s2s_use_starttls, false}.
{s2s_certfile, "/etc/ejabberd/ejabberd.pem"}.
%{domain_certfile, "example.org", "./example_org.pem"}.
%{domain_certfile, "example.com", "./example_com.pem"}.

% If SRV lookup fails, then port 5269 is used to communicate with remote server
{outgoing_s2s_port, 5269}.

% Used modules:
{modules,
[
{mod_register, [{access, register}]},
{mod_roster, []},
{mod_privacy, []},
{mod_adhoc, []},
{mod_configure, []}, % Depends on mod_adhoc
{mod_configure2, []},
{mod_disco, []},
{mod_stats, []},
{mod_vcard, []},
{mod_offline, []},
{mod_announce, [{access, announce}]}, % Depends on mod_adhoc
{mod_echo, [{host, "echo.localhost"}]},
{mod_private, []},
{mod_irc, []},
% Default options for mod_muc:
% host: "conference." ++ ?MYNAME
% access: all
% access_create: all
% access_admin: none (only room creator has owner privileges)
{mod_muc, [{access, muc},
{access_create, muc},
{access_admin, muc_admin}]},
% {mod_muc_log, []},
% {mod_shared_roster, []},
{mod_pubsub, []},
{mod_time, []},
{mod_last, []},
{mod_version, []}
]}.

% Local Variables:
% mode: erlang
% End:

=======================
This is what appears in /var/log/ejabberd/ejabberd.log when trying to join ejabberd@conference.jabber.ru :
=INFO REPORT==== 2006-09-19 14:34:58 ===
I(<0.324.0>:ejabberd_s2s_out:106): started: {"neonus.sk",
"conference.jabber.ru",
{new,"3898684725"}}

=INFO REPORT==== 2006-09-19 14:35:50 ===
I(<0.237.0>:ejabberd_listener:90): (#Port<0.386>) Accepted connection {{213,180,203,18},51847} -> {{82,119,226,73},5269}

=INFO REPORT==== 2006-09-19 14:35:50 ===
I(<0.326.0>:ejabberd_s2s_in:106): started: {gen_tcp,#Port<0.386>}

=INFO REPORT==== 2006-09-19 14:35:50 ===
I(<0.326.0>:ejabberd_s2s_in:318): GET KEY: {"neonus.sk",
"conference.jabber.ru",
[],
"1524811126"}

=INFO REPORT==== 2006-09-19 14:35:50 ===
I(<0.328.0>:ejabberd_s2s_out:106): started: {"neonus.sk",
"conference.jabber.ru",
{verify,
<0.326.0>,
"1524811126",
"3609195603"}}

=INFO REPORT==== 2006-09-19 14:35:50 ===
I(<0.326.0>:ejabberd_s2s_in:338): VERIFY KEY: {"neonus.sk",
"conference.jabber.ru",
"834839965",
"3898684725"}

=INFO REPORT==== 2006-09-19 14:35:50 ===
I(<0.324.0>:ejabberd_s2s_out:254): recv result: {"conference.jabber.ru",
"neonus.sk",
[],
"valid"}

=INFO REPORT==== 2006-09-19 14:36:42 ===
I(<0.328.0>:ejabberd_s2s_out:265): recv verify: {"conference.jabber.ru",
"neonus.sk",
"3609195603",
"valid"}

Where can be the problem? Wrong DNS entries? Wrong certificate (or whatever)? Does anyone have some idea how can I fix this?