The following UM IP gateways did not respond as expected to a SIP OPTIONS request.
...along with the Lync client not being able to call voicemail or users being able to leave a message for the Lync user.
Turns out the UM IP gateway in Exchange 2010 which is set up by running the ExchUCUtil.ps1 script doesn't have a port listed in the configuration. This can be viewed by running: Get-UMIPGateway | fl
To resolve it, run Set-UMIPGateway -Port 5061
Cheers!