Schoolboy error. The whole internal/external domain name thing is where I've messed up.
The AD domain is "domain.local", the external email domain is "domain.com" and I've setup DNS records either side to cover internal & external clients for Autodiscovery, MX, dmarc etc. I used the internal username (user@domain.local) when setting the account up on the Android device, this works fine for setting things up, but when you attempt to send an email it has an incorrect domain suffix and the email gets rejected (user@domain.local as opposed to user@domain.com).
I've updated all the primary email addresses for the handful of clients to the external email domain, added the additional 'proxyAddresses' covering the internal domain name, deleted the users from grommunio that had the @domain.local address and re-synced LDAP.
The problem I've got now is onboarding internal clients as I've got DNS issues. I'll need to replicate the external "domain.com" DNS zone internally with the internal IPv4 address of the mail server and not the external. I'm masking some of the issues as I'm running IPv6 on most internal networks so the internal and external hostnames resolve to the same IPv6 addresses. The WiFi where the Android device is connected only has IPv4, so resolving the internal hostname (mail.domain.local) works and lets the client sync, but it won't allow emails to be sent as its the wrong email domain name that the client has been setup with.