Someone needs to tell one of our routers this. It has been routing between
multiple NICs for well over a year without any problem.

In that case, I would dearly love to hear how it was done.

You haven't explained exactly what the routing problem was, so it's kind
of hard to explain what you did wrong. Linux's routing code is pretty
flexible and can be made to do all kinds of unusual stuff.