Are you using Lotus Notes in an organisation that values data security more than public access? If so, you may be fighting your network security configuration. For example, there may be routing rules that insulate the Lotus Notes email server from your Moodle server. Is there any outgoing traffic from the Moodle server addressed to the Lotus Notes email server? Is the traffic being accepted at the Lotus end or being dropped, or not arriving?
As a work-around, ave you been able to get the Moodle server to send the mail? - http://docs.moodle.org/22/en/Messaging_settings#Email_settings
Using and maintaining the default mail sending capacity in Moodle might be easier than getting it to use the Lotus Notes mail system. Moodle does not need to receive any email and consequently has much simpler security considerations.
I no longer have access to a Lotus Notes email system because the users preferred anything else.
Sorry - this is all probably obvious, given that you have been working on this for weeks.