This bug may only affect the GPL version. I haven't tested to see if it has been fixed in the Professional version, and I'm not sure if it affects Postfix. It has been a problem for me for a long time, but I kept forgetting to report it until now.
When creating a new domain, Virtualmin correctly adds the domain name to the local-host-names (formerly sendmail.cw?) file. However, sendmail is not restarted automatically, and this file is not reloaded by the already running daemon. So, mail is rejected for the new domain with a relaying denied error until sendmail is manually restarted.