We were able to solve this. The issue was that we didn't have TNEF enabled on the Remote-Domain that pointed to our exchange online and vice versa.
As well, we found that enabling TNEF on the default Remote Domain caused a lot of problems with internet users receiving Winmail.dat attachments. So we created Remote domains within Exchange Online and on-premise that use their respective domains with TNEF enabled and disabled it on the default routes which solved this issue.