I had a similar problem when addressing to an @faxdomain style address. I was sending from Outlook 2000 to MS Exchange.
I overcame it by right-click the address in the "To" line, which brings up a box with "Display name" and "E-mail address". I noticed that the e-mail address had been truncated cutting off part of the address.
I edited this to have the full address including the @faxdomain
Sending this worked ok when the server was MS Exchange, but I've no idea if it will work when the server is Lotus Notes.