I checked with my hosting-provider and he said the "e-mail" to a specific user was never "initiated" as per the log-files.
The issue was with old users already registered. When I created a new user-profile this problem did not occur.
So what I did is clicking onto "Save User" in ACP and the "notification mail" got being send to the specific user for which I "saved" his profile again in ACP.
The issue occured with Gmail and GMX-accounts.
So "Save User" in ACP is triggering something which makes "notification e-mails" working again. What is it what "Save User" is doing and how does it relate to "notification e-mails" being send or not ?