Emails Never Reaching Users (Queued_mail_for_delivery)

I run a popular community and there are a number of notifications the user can receive.
The notifications are sent via PHP mail() function. For an increasing number of users, emails never get to their mailbox (neither in their junk mail folder).
When I look in qmail's logs, I see a lot of these :

Quote:

@40000000469233dd346d5d24 new msg 331743
@40000000469233dd346d610c info msg 331743: bytes 637 from <myscript@mydomain.com> qp 14664 uid 81
@40000000469233dd34bb8cc4 starting delivery 151: msg 331743 to remote user@hotmail.com
@40000000469233dd34bb90ac status: local 0/10 remote 1/20
@40000000469233df02a4e334 delivery 151: success: 65.54.244.40_accepted_message./Remote_host_said:_250__<20070709131043.14663.qmail@ns22299.ovh.net>_Queued_mail_for_delivery/
@40000000469233df02a4eb04 status: local 0/10 remote 0/20
@40000000469233df02a4eb04 end msg 331743

So I receive a "250" answer, but with this "Queued_mail_for_delivery" message, and the user never gets anything of the email. This exact message is for an hotmail account, but I get other similar ("queued") messages for other accounts.

Is there anything i can do to prevent this from happenning ? A lot of new registrant get these messages with their validation emails and that is lost customers for me.