Mail stuck at queue because no 220 banner at remote

[RattleSn@ke]

Hi,

I'm having the following odd problem with some remote mail-servers (mostly exchange).

Mail to these servers get stuck in the queue, because upon connection, there is no 220 welcome banner.

Normally when you connect to a mailserver with lets say telnet, you get a 220 welcome banner.
When I connect to such a server with telnet, I get the following:
[onno@medusa ~]$ telnet <mailserver> 25
Trying xx.xx.xx.xx...
Connected to <mailserver> (xx.xx.xx.xx).
Escape character is '^]'.

And that's it!!
Only when I issue a ehlo command, the remote server is responding...
And this is the exact reason why qmail-remote failes to deliver any mail to that host...

And it occured since my new server with plesk 8.2.0 is installed...
My old server didn't have this problem.

Has anyone an idea, because I'm out of solutions...

Thanks!
Onno.