@Elliot Stansfield ,
Welcome to the Microsoft Q&A forum. Thank you for posting a detailed question.
I went through some similar issues internally and as correctly pointed out the issue can be related to Cisco Umbrella as it can override the DNS resolution as it needs to know which domains should be considered as internal. The issue was resolved after adding the internal domain to Cisco Umbrella 's domain management.
You can through this link regarding Umbrella's Domain Management feature and how to add the appropriate domains to the Internal Domains section of the dashboard.
Hope this helps! Please let me know if the issue still persists. Thank you!