Hi Stefan,
Thank you for posting your question in the Microsoft Q&A forum.
May I know do you use on-prem Exchange server with your AD accounts? Or you just use third-party mail server in your current AD forest?
I would like to know if you mail server and your AD account belongs to the same environment.
Based on your description, the O365 mailboxes have smtp addresses both with mycompany.com and newstart.com domain. So, it’s normal that, when we send emails from your O365 mailbox to mycompany.com, the O365 mailbox will be resolved in your organization successfully and no need to relay to external.
If you want to use newstart.com for O365 mailbox and use mycompany.com only for external mail server mailbox, it’s not suggested to add smtp address mycompany.com for these O365 mailbox. At the same time, you could create mail contacts in O365 for external mailboxes with mycompany.com (InternalRelay). So that emails from your O365 mailbox to mycompany.com could be sent out if only mail contact is resolved.
You can check this article for more details about mail contact:
Recipients in Exchange Online | Microsoft Learn
Manage mail contacts in Exchange Online | Microsoft Learn
If the answer is helpful, please click "Accept Answer" and kindly upvote it. If you have extra questions about this answer, please click "Comment".
Note: Please follow the steps in our documentation to enable e-mail notifications if you want to receive the related email notification for this thread.