remote server not found (invalid dialback key) - DNS works :/ Other ideas ?

Edit: Just tested with tcpdump. Resolving works fine, i see packets between both servers while trying to send a message. But still getting the error messages.
But... it does not happen to all servers. Most of them are working fine.
I am quite lost...

Original Message:

Hi Guys,

i just installed my new ejabberd server on freebsd 8.2 .

Migration of all roster data went fine.
Messaging is working.. except with 2 other servers.

(invalid dialback key)

i searched many howtos...all pointing to SRV record/dns record problems.

I have SRV records for my domain... the other server has not.

But in the FAQ it is stated that ejabberd tries the SRV lookup, but then makes a fallback to normal DNS resolving.
That seems not to happen in my case.

dig resolvs the target domain fine on that server. But ejabberd doesnt care. Looks like ejabberd is ONLY looking for SRV records.

When trying to send messages to contacts of that server i get an 404 Error code... remote server not reachable

Is there any idea how to fix this ? Would be great.

(just to state clear: on the old server i had no srv entries... and i could connect to them fine! now i had the problem...then added the srv entries. But i think this has nothing todo with MY dns entries... becaus i can not reach THEM, right ?!)

Telnet to 5269 at the targetdomain works fine.