Had the issue solved with the help of Microsoft CSP Support, since our CSP also wasn't able to solve the issue. For those interested, since there isn't much about this specific error on the web:
Issue 1 - Timezone It looks like the logs recommend you to have your AD Servers and the Exchange Server (where we've run the Hybrid Wizard) set to the UTC Timezone. Not sure if this is really needed, but it was highlighted as an error in the hybrid wizard log
Issue 2 - DNS Lookup Even though our TXT record for verification was properly set, all parties where unaware, that the specific DNS Server that hosted our DNS records (external provider) was stuck and didn't really resolve the DNS lookup from the Hybrid Wizard. Our provider had to restart their DNS services, after that everything worked again.
Best Response confirmed by
Ivan Unger (Valued Contributor)