I suffered from the same problem and want to document the solution I found lately.
The problem doesn't seem to be related to the motd.service at all. The output looks exactly the same on a working system.
Instead I took a look at my sshd_config in /etc/ssh/ because we dealt with ssh-logins and I remembered that during a apt upgrade I had to decide if to switch to a new version of sshd_config or to stay with my old.
However, it turns out that the welcome message depends on the UsePAM parameter in sshd_config.
If it is set to 'no' you won't receive the fancy welcome message. Simply turning it to 'yes' did the trick for me and I now receive the welcome message again with every ssh-login.
Summary:
Make sure that this is in your /etc/ssh/sshd_config:
[...]
UsePAM yes
[...]
Hope this helps some other folks.