Is this even possible?
Department is a Child of
The UI Wizard only includes
Department fields on outbound message selector.
Found this link
Is there a way to manually edit the outbound message definition to do this?
No this is not currently possible, you'd have to use the option to send a sessionId in the message and have your listener make an API call back to saleforce to get the related records it needs.