relay server issue?

This domain, as much others, are allocated on one (of 20) dedicated servers.

Since a couple of weeks, many customers, have in troubles to send emails, from their own domain names, to hotmail.com accounts.

One server have a lot of accounts (close to 200) with 1/4 emails each domain.

This is the problem:

1) From one email (hosted on that dedicated server) I send an email to a hotmail.com account

2) Mails leaves the server with NO errors. Server's logs said: Completed, OK!

3) That email never reaches hotmail inbox nor spamm nor any folder... email, never arrives.

4) If I send some email, FIRST, from that hotmail.com to my personal email OUTSIDE hotmail.com, I receives that email at my personal one

5) Then, I REPLY that email and ARRIVES to hotmail.com account

As described to here, it looks like a relay issue.