I'm worried it's going to get hideously complex and hard to test

@DonkeyBot why not put a custom field on the department record with that department's specified approver? I think you could do that and still tie into the native approval limits pretty easily.

I don't think this would be too difficult to set up. Agree on the point of new departments/employee turnover, so it would be more about maintenance than setup, but there are ways around that if you're really determined. FWIW here's what our PO WF looks like:

Wow. Nice workflow, Be curious to see some of the state and transition detail (obviously hiding personal/company info)

The PR one is a bit wilder: