Outbound mail not sending (newly-installed Exchange 2019 server)

@joeqwerty put me on the right track.

Firstly, it is certainly possible to do what I wanted. Centralised Mail Transport (CMT) allows you to route incoming and outgoing emails through Office 365, it's just that enabling that feature in the Hybrid Exchange wizard isn't enough.

To get inbound emails to route through Office 365, just add the EXO-related MX records to DNS, and make the EXO MX records a higher priority. As for outbound emails, you need to create an additional Send Connector that uses EXO as a "Smart Host" (click here) for more details.

Once both are configured, you can use the EXO Message trace feature to search inbound and outbound emails whether they be from Exchange Online (EXO) or Exchange On-premise (EOP) mailboxes. Doesn't matter.

NB You may need a static IP address to get this to work correctly. That is, if you're using Hybrid Classic mode.

I hope this helps someone else.