Federation trouble

We have some trouble getting federation to work on one install. No matter waht we try, when trying to add an external contact, we get a remote server not found error. Checked everything: federation is enabled, accepts connections with any host, post is open in the firewall, telnet, dig - all ok. Tried it on another server, works like a charm. Obviously there’s a difference between setups, but I don’t know where to look anymore. Any hints?

TIA