I'm not aware of a general best approach

Give monadic error handling a try. You know already it composes nicely even when there are an arbitrary amount of frames between complicated_flow() and routine() and does not suffer from the downsides of C-style retval (extra code for checking) or exceptions (possibly global jumps in control flow).

It's maybe not appropriate for your current use case because it would require a bit of code to be changed and it does not look much perlish at first glance, but perhaps your colleague okay with that.