It looks like Lotus Notes does not support Internationalized Domain Names. If you want to send an email to somebody where the domainname has e.g. german umlauts you have to use a punycode encoder tool, replace the domainname with the encoded domainname string and then send it.
Otherwise the mailrouter gives you a ’no route found to domain…‘ failure.
[RFC 3492]
Online converter:
IDN Online Converter (german)