It is time to remind me to always check Exchange for existence of receive connectors and their scoping. In this case users where able to record voice messages, but they never arrived in recipients mailbox. Checked the Exchange server event Viewer.
This indicated that there is something wrong with the SMTP server. There I found a “Mailrelay” receive connector configured to not use authentication or encryption also scoped to hit the IP subnet containing the server IP address. Created two new ranges, excluding the exchange server ip address.
Here we go. This done the trick.